THE COMPLEXITY OF THE FIRST KIND OF ALGORITHMS

Author(s): Tsvetkov V.Ya.

Rubric: Information technology

DOI: 10.21777/2500-2112-2020-4-73-80

Release: 2020-4 (33)

Pages: 73-80

Keywords: algorithms, complexity classes, types of complexity, type I algorithm, type II algorithm, computational model, Turing machine

Annotation: The article analyzes the complexity of algorithms of the first kind. The features are analyzed according to which the algorithm can be classified as an algorithm of the first kind. A new concept is introduced in the theory of algorithmic complexity “algorithm efficiency”. The difference between algorithms of the first and second kind is shown on the example of deterministic and non-deterministic Turing machines. The computational model is disclosed on the example of a Turing machine. A generalized model of algorithms of the first kind is given. The content is revealed and the necessity of the concept of asymptotic complexity is substantiated. Basic analysis is performed with classes and types of time complexity. Examples are given and the analysis of algorithms of constant time and linear time is given. The conventionality of some types of complexity is noted. It consists in the fact that algorithms that belong to the same class or type of complexity physically use different computation times. A situation is noted in which a simpler type of complexity spends more time on calculations than a more complex one. The drawback of the existing theory of algorithmic complexity is noted – the exclusion of the cognitive factor and cognitive complexity from the analysis of complexity. This is due to the exclusion of the concept of the effectiveness of an algorithm when analyzing or assessing complexity. The existing theory of complexity focuses on computation and computation time. But the main thing in the calculations is the result. If the result of the calculations is not qualitative or unclear, then the computation time loses its importance. Accordingly, the assessment of complexity classes should be tied not only to time, but also to the quality of the result. Results of further research are outlined.

Bibliography: Tsvetkov V.Ya. THE COMPLEXITY OF THE FIRST KIND OF ALGORITHMS // Education Resources and Technologies. – 2020. – № 4 (33). – С. 73-80. doi: 10.21777/2500-2112-2020-4-73-80