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