Обчислювальна складність

Для оцінки алгоритмів існує багато критеріїв. Найбільшу увагу приділяють порядку росту необхідних для розв'язання задачі часу та розміру пам'яті при збільшенні розміру вхідних даних.

Нехай А — алгоритм розв'язання деякого класу задач, а ${\displaystyle N}$ — розмірність окремої задачі цього класу. ${\displaystyle N}$ може бути, наприклад, розмірністю оброблюваного масиву, числом вершин оброблюваного графа тощо, Позначимо ${\displaystyle f_{A}\left(N\right)}$ функцію, що дає верхню межу максимального числа основних операцій (додавання, множення і т. д.), які повинен виконати алгоритм А, розв'язуючи задачу розмірності ${\displaystyle N}$. Говоритимемо, що алгоритм А поліноміальний, якщо ${\displaystyle f_{A}\left(N\right)}$ зростає не швидше, ніж деякий поліном від ${\displaystyle N}$. В іншому разі А — експоненціальний алгоритм.

Виявляється, що між цими класами алгоритмів є істотна різниця: при великих розмірностях задач (які, зазвичай, найцікавіші на практиці), поліноміальні алгоритми можуть бути виконані на сучасних комп'ютерах, тоді як експоненціальні алгоритми для практичних розмірностей задач, як правило, не можуть виконатися повністю. Зазвичай розв'язок задач, що породжують експоненціальні алгоритми, пов'язаний з повним перебором всіх можливих варіантів, і, зважаючи на практичну неможливість реалізації такої стратегії, їх розв'язують іншими шляхами.

Наприклад, якщо навіть існує експоненціальний алгоритм для пошуку оптимального розв'язку деякої задачі, то на практиці застосовуються інші, ефективніші поліноміальні алгоритми для пошуку прийнятного розв'язку (не обов'язково оптимального, а лише наближеного до оптимального). Та навіть якщо задача має розв'язок за допомогою поліноміального алгоритму, побудувати його можна лише після заглиблення в суть поставленої задачі.

Поліноміальні алгоритми також можуть істотно розрізнятися залежно від степеня полінома, що апроксимує залежність ${\displaystyle f_{A}\left(N\right)}$. Розглянемо оцінювання часової складності алгоритму. Така оцінка проводиться із застосуванням відношення ${\displaystyle O}$ («велике О»): кажуть, що ${\displaystyle f_{A}\left(N\right)}$ зростає як ${\displaystyle g\left(N\right)}$ для великих N і записується це як ${\displaystyle f_{A}\left(N\right)=O\left(g\left(N\right)\right)}$. Якщо існує додатна стала Const>0, така, що ${\displaystyle \lim _{N\to \infty }f_{A}(N)/g(N)=Const}$, то оцінка О(g(N)) називається асимптотичною часовою складністю алгоритму.

Оцінка О(g(N)) для функції ${\displaystyle f_{A}\left(N\right)}$ застосовується, коли точне значення ${\displaystyle f_{A}\left(N\right)}$ невідоме, а відомий лише порядок зростання часу, затрачуваного на розв'язання задачі розмірністю N за допомогою алгоритму А. Точні значення ${\displaystyle f_{A}\left(N\right)}$ залежать від конкретної реалізації, тоді як О(g(N)) є характеристикою самого алгоритму. Наприклад, якщо часова асимптотична складність алгоритму дорівнює ${\displaystyle O(N^{2})}$ (такий алгоритм називається квадратичним), то при збільшенні N час розв'язання задачі збільшується як квадрат N. Факт експоненціальної складності алгоритму в термінах введеної символіки можна записати як ${\displaystyle f_{A}\left(N\right)=O\left(k^{N}\right)}$, де k — більше за одиницю число (зазвичай ціле).

Інший вид оцінки пов'язаний з введенням «малого о»: кажуть, що ${\displaystyle f_{A}\left(N\right)}$ зростає не швидше від ${\displaystyle g(N)}$ для великих N, що записується ${\displaystyle f_{A}\left(N\right)=o\left(g\left(N\right)\right)}$, якщо ${\displaystyle \lim _{N\to \infty }f_{A}(N)/g(N)=0}$. Наприклад, очевидно, що ${\displaystyle x^{2}=o(x^{5}),\sin(x)=o(x)}$. Інший приклад: алгоритм А є поліноміальним, якщо ${\displaystyle f_{A}\left(N\right)=o\left(P_{k}\left(N\right)\right)}$, де P_k(N) — деякий поліном від N степеня k. Так, алгоритм, асимптотична складність якого дорівнює о(N log N), належить до поліноміальних.

В наступній таблиці наведено поширені асимптотичні складності з коментарями.

Графіки функцій наведених в таблиці.

• Нотація Ландау
• Часова складність алгоритму
• Аналіз алгоритмів
• Складність апроксимації

• Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528.