Abstract
The article analyzes the complexity of the first kind algorithms. The first kind’ algorithms features are investigated. A new concept is introduced in the theory of algorithmic complexity “algorithm efficiency” and “physical computation time”. A new concept in the algorithmic complexity theory “physical complexity of the algorithm” is introduced. The difference between the first and second kind algorithms is shown on the deterministic and non-deterministic Turing machines example. A first kind algorithms generalized model is given. The conventionality of complexity’ some types are noted. It consists in the fact that algorithms that belong to the same complexity class or type of complexity physically use different computation times. A situation is noted in which a complexity simpler type spends more time on computations than a more complex one. The algorithmic complexity existing theory lack is noted - the calculation result and cognitive complexity quality exclusion from the complexity analysis. The complexity’ existing theory focuses on computation and computation time. The main thing in the computations is the result. If the computations’ result is not high-quality or unclear, then the computation time loses its importance. Accordingly, the complexity classes assessment should be tied not only to time but also to the resulting quality. The algorithm physical complexity takes into account the computation result quality #CSOC1120.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Kudzh, S.A., Tsvetkov, V.Y., Rogov, I.E.: Life cycle support software components. Russian Technol. J. 8(5), 19–33 (2020)
Hidary, J.D.: Complexity theory. In: Hidary, J.D. (ed.) Quantum Computing: An Applied Approach, pp. 37–44. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-23922-0_4
Doerr, C.: Complexity theory for discrete black-box optimization heuristics. In: Doerr, B., Neumann, F. (eds.) Theory of Evolutionary Computation, pp. 133–212. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-29414-4_3
Tsvetkov, V.Ya.: Incremental solution of the second kind problem on the example of living system. Biosci. Biotechnol. Res. Asia 11(S), 177–80 (2014)
Shchennikov, A.E.: Direct algorithms models. Slavic Forum 4(18), 103–109 (2017)
Xia, T.: A constant time complexity spam detection algorithm for boosting throughput on rule-based filtering systems. IEEE Access 8, 82653–82661 (2020)
Consolini, L., et al.: Optimal time-complexity speed planning for robot manipulators. IEEE Trans. Rob. 35(3), 790–797 (2019)
Kasperski, A., Zieliński, P.: Robust discrete optimization under discrete and interval uncertainty: a survey. In: Doumpos, M., Zopounidis, C., Grigoroudis, E. (eds.) Robustness analysis in decision aiding, optimization, and analytics. ISORMS, vol. 241, pp. 113–143. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-33121-8_6
Tilahun, S.L., Ngnotchouye, J.M.T.: Firefly algorithm for discrete optimization problems: a survey. KSCE J. Civ. Eng. 21(2), 535–545 (2017). https://doi.org/10.1007/s12205-017-1501-1
Nishikawa, H.: On Estimating Machine-Zero Residual. arXiv preprint arXiv:2007.06394 (2020)
Zhang, X., et al.: The convergence analysis and uniqueness of blow-up solutions for a Dirichlet problem of the general k-Hessian equations. Appl. Math. Lett. 102, 106124 (2020)
Titov, E.K., Tsvetkov, V.Ya.: Accumulated reliability of information hardware and software systems. In: IOP Conference Series: Materials Science and Engineering, vol. 919, p. 022055 (2020). https://doi.org/10.1088/1757-899X/919/6/022055
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2021 The Author(s), under exclusive license to Springer Nature Switzerland AG
About this paper
Cite this paper
Deshko, I.P., Tsvetkov, V.Y. (2021). Physical Complexity of Algorithms. In: Silhavy, R. (eds) Software Engineering and Algorithms. CSOC 2021. Lecture Notes in Networks and Systems, vol 230. Springer, Cham. https://doi.org/10.1007/978-3-030-77442-4_32
Download citation
DOI: https://doi.org/10.1007/978-3-030-77442-4_32
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-030-77441-7
Online ISBN: 978-3-030-77442-4
eBook Packages: Intelligent Technologies and RoboticsIntelligent Technologies and Robotics (R0)