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

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

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

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

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

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

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

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

• Hopcroft, John E.; Motwani, Rajeev; Ullman, Jeffrey D. (2001). Вступ до теорії автоматів, мов і обчислень (вид. 2nd). Addison–Wesley. с. 521. {{cite book}}: Зовнішнє посилання в |edition= (довідка)(англ.)

Це незавершена стаття з математики. Ви можете допомогти проєкту, виправивши або дописавши її.

Це незавершена стаття про інформаційні технології. Ви можете допомогти проєкту, виправивши або дописавши її.