2.3 Складнiсть задач
Таким чином, другий алгоритм ефективнiший за перший.
Пiд складнiстю задачi розумiтимемо час, необхiдний для обчислення функцiï, за допомогою якоï знаходиться ïï розв’ язок. Пiд складнiстю розумiтимемо складнiсть алгоритму у найгiршому випадку. Oскiльки не можна побудувати для кожноï функцiï найкращоï машини, що ïï обчислює, то введемо поняття класу складностi.
Означення 2.7. Клас складностi мiстить функцiï f, для яких iснує машина M, що обчислює f, така, що функцiя T( M, x) за часом обмежена функцiєю t( n) iз точнiстю до мультиплiкативноï константи, тобто
O( t( n)) = { f | ∃M:( M обчислює f &( t M( n) = O( t( n)))}, де t( n) – порядок класу.
Класом задач складностi t( n) назвемо сукупнiсть задач, якi розв’ я- зуються за час порядку t( n).
O-оцiнки виражають вiдносну швидкiсть алгоритму залежно вiд початкових даних. Розглянемо класи O-складностi алгоритмiв. Нехай N – кiлькiсть оброблюваних даних( табл. 2.1).
Розглянемо прийоми проведення аналiзу алгоритмiв i визначення ïх складностi. Тимчасова складнiсть алгоритму може бути порахована, виходячи з аналiзу його керувальних структур. Ми пам’ ятаємо, що до керувальних структур належать лiнiйнi та умовнi вирази, цикли( табл. 2.2).
Якщо немає рекурсiï й циклiв, то всi керувальнi структури можуть бути зведенi до структур константноï складностi. Oтже, i весь алгоритм також характеризується константною складнiстю. Тому визначення складностi алгоритму в основному зводиться до аналiзу циклiв i рекурсивних викликiв. Розглянемо алгоритм обробки елементiв масиву.
Алгоритм:
1. Для i = 1 до N виконувати 2. початок 3. { Простий вираз } 4. кiнець;
Складнiсть цього алгоритму становить O( N), оскiльки тiло циклу виконується N разiв, а складнiсть тiла циклу дорiвнює O( 1).
35