Асимптотична оцінка складності

Складність обчислювальних процесів — це поняття теорії складності обчислень, оцінка ресурсів (зазвичай часу та пам'яті) необхідних для виконання алгоритму.

• Часова складність — час
• Просторова складність — пам'ять

Обчислювальна складність
Досліджується в	теорія складності обчислень і аналіз алгоритмів

Визначення

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

Нехай А — алгоритм розв'язання деякого класу задач, а ${\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), належить до поліноміальних.

Приклади асимптотичних складностей

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

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

Складність	Коментар	Приклади
O(1)	Сталий час роботи не залежно від розміру задачі	Очікуваний час пошуку в хеші
O(log log n)	Дуже повільне зростання необхідного часу	Очікуваний час роботи інтерполюючого пошуку n елементів
O(log n)	Логарифмічне зростання — подвоєння розміру задачі збільшує час роботи на сталу величину	Обчислення x^n; двійковий пошук в масиві з n елементів
O(n)	Лінійне зростання — подвоєння розміру задачі подвоїть і необхідний час	Додавання/віднімання чисел з n цифр; лінійний пошук в масиві з n елементів
O(n log n)	Лінеаритмічне зростання — подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі	Сортування злиттям або n елементів; нижня границя сортування порівнянням n елементів
O(n²)	Квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час	Елементарні алгоритми сортування
O(n³)	Кубічне зростання — подвоєння розміру задачі збільшує необхідний час у вісім разів	Звичайне множення матриць
O(c^n)	Експоненціальне зростання — збільшення розміру задачі на 1 призводить до c-кратного збільшення необхідного часу; подвоєння розміру задачі підносить необхідний час у квадрат	Деякі задачі комівояжера, алгоритми пошуку повним перебором

Див. також

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

Джерела

• Hopcroft, John E.; ; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521.(англ.)