REDUCING THE COMPUTATIONAL COMPLEXITY OF THE ALGORITHM FOR DETERMINING PERFECT NUMBERS AND STUDYING THIS CONCEPT IN SECONDARY SCHOOL

Abstract

Introduction. Today, the concept of computational complexity of the algorithm is considered in the course of high school computer science in Ukraine only on an intuitive level, although this concept teaches future programmers to pay attention not only to the correctness of the problem, but also its effectiveness. Purpose. Demonstration of the possibility of studying the concept of computational complexity of the algorithm in high school on the example of the problem of determining perfect numbers in a given interval. Proving the parity of perfect numbers and determining the minimum non-trivial divisors for finding them. Methods. The deductive method is used in the process of deriving the theorems on parity and properties of perfect number. Estimation of complexity of algorithms of definition of perfect numbers on the set interval is carried out by methods of the theory of algorithms. Results. The publication proves the theorem of the parity of perfect numbers. It is shown that the squares of natural numbers cannot be perfect numbers. It is established that to determine the perfection of the number N its non-trivial divisors should be found in the interval from two to the square root of N-1 and add to the sum not only the found divisor but also the obtained fraction. The improvements in the algorithm for finding perfect numbers in a given interval presented in the article make it possible to reduce its asymptotic computational comсpкleлxаiдtyн ісfrтoьm з OO((NN22)) дtoо O(N N ). ВT h e correctness of the theoretical calculations and the correctness of the fragments of programs was confirmed experimentally using the remote independent computing environment at https://www.e-olymp.com. Originality. The theorems of the parity of perfect numbers and on the imperfection of squares of natural numbers are proved for the first time. To determine the perfection of the number N, the search range of nontrivial divisors was reduced to the square root of N-1, which allowed to speed up the calculations and not to check the differences of the fraction from the divisor. Conclusion. A drastic reduction in the computational complexity of the algorithm is possible primarily by reducing the asymptotic computational complexity. The concept of asymptotic computational complexity in the context of execution time should be formed in students during computer science lessons in all secondary schools, starting from 7th form, in the process of studying nested cycles, for example, by determining perfect numbers at a given interval. This will develop students' skills in writing not only correct but also effective programs.