2.3 Складнiсть задач
Треба перевiрити n ( n − 1 )( n − 2 ) варiантiв , що вiдповiдає кубiчнiй складностi O ( n 3 ).
У загальному випадку , якщо ефективнiсть алгоритму визначається багаточленом фiксованого порядку k вiд обсягу вхiдних даних n , то вона задовольняються оцiнкою O ( n k ), не зважаючи , згiдно з властивiстю 2 , на старший коефiцiєнт i решту членiв полiнома .
O-оцiнювання дозволяє не використовувати конкретний обчислювальний пристрiй для аналiзу складностi .
Нехай є деяка вiртуальна машина M , яка обчислює функцiю f , i визначенi вхiднi данi : x – деяке двiйкове слово . Визначимо функцiю T ( M , x ) як кiлькiсть операцiй , що потрiбнi машинi M для роботи на вхiдному словi x . Справедлива така теорема , яка є наслiдком з так званоï теореми Блюма про прискорення ( 1967 ).
Теорема 2.1 . Iснує така всюди визначена на двiйкових словах обчислювана функцiя f , що будь-яку машину M , яка ïï обчислює , можна прискорити так : iснує iнша машина M ′ що також обчислює f , для якоï виконується нерiвнiсть t M ′( n ) ≤ log 2 t M ( n ) для майже всiх n ( тобто всiх натуральних чисел за виключенням елементiв деякоï скiнченоï множини натуральних чисел ), де t M ( n ) = max | x | ≤n T ( M , x ), | x | позначає довжину слова x .
За бiльш вiльного формулювання скажiмо так : iснує задача для якоï iснує багато алгоритмiв вирiшення , але неможливо придумати найшвидший алгоритм , оскiльки для кожного алгоритму вирiшення iснує ще швидший алгоритм , який ïï вирiшує . Слiд зауважити , що така властивiсть має мiсце не для кожноï задачi .
2.3 Складнiсть задач
Поняття складностi алгоритму пов ’ язане з поняттям складностi задачi . Iз теореми Блюма можна зробити висновок , що визначати складнiсть задачi через складнiсть найкращого алгоритму для ïï розв ’ я- зання – не найвдалiший спосiб .
Нехай необхiдно побудувати алгоритм для розв ’ язання такого класу задач : обчислити значення виразу a n x n +...+ a 1 x + a 0 у точцi x = b , де a i ∈ Z , b ∈ Z , а Z – множина цiлих чисел . Наведемо алгоритм для даного класу задач .
Вхiднi данi : ( a n , a n−1 , ..., a 0 ), де a i ∈ Z , b ∈ Z , ( a n , a n−1 , ..., a 0 ) – вектор з n + 1 цiлих чисел , b – цiле число . Результат : r = f ( b ), де f ( b ) = a n b n + ... + a 1 b + a 0 . Змiннi : i , x , r – цiлого типу .
33