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