Складність обчислювальних процесів - це поняття теорії складності обчислень. оцінка ресурсів (зазвичай часу) необхідних для виконання алгоритму.
визначення
Нехай А - алгоритм вирішення певного класу задач, а - розмірність окремої завдання цього класу. може бути, наприклад, розмірністю оброблюваного масиву. числом вершин оброблюваного графа т.д. Позначимо функцію, дає верхню межу максимального числа основних операцій (додавання, множення і т. Д.), Які повинен виконати алгоритм А, вирішуючи завдання розмірності. Будемо говорити, що алгоритм А поліноміальний. якщо зростає не швидше, ніж деякий поліном від. Інакше А - експонентний алгоритм.
Виявляється, що між цими класами алгоритмів є істотна різниця: при великих размерностях завдань (які, як правило, найцікавіші на практиці), поліноміальні алгоритми можуть бути виконані на сучасних комп'ютерах, тоді як експоненціальні алгоритми для практичних размерностей завдань, як правило, не можуть виповнитися повністю. Зазвичай рішення задач, що породжують експоненціальні алгоритми, пов'язаний з повним перебором всіх можливих варіантів, і з огляду на практичну неможливість реалізації такої стратегії, для їх вирішення розробляються інші підходи.
Наприклад, якщо навіть існує експонентний алгоритм для знаходження оптимального рішення деякої задачі, то на практиці застосовуються інші, більш ефективні поліноміальні алгоритми для знаходження не обов'язково оптимального, а лише прийнятного рішення (наближеного до оптимального). Але навіть якщо завдання допускає рішення за допомогою полиномиального алгоритму, його можна побудувати тільки після глибокого вникання в суть поставленого завдання.
Поліноміальні алгоритми також можуть істотно відрізнятися в залежності від ступеня полінома, що апроксимує залежність. Розглянемо оцінки часової складності алгоритму. Така оцінка проводиться із застосуванням відносини ( "Велике Про"): кажуть, що росте як для великих N і записується це як. Якщо існує позитивна константа Const> 0, така, що. Те оцінка О (g (N)) називається асимптотичної часової складності алгоритму.
Оцінка В (g (N)) для функції застосовується, коли точне значення невідоме, а відомо лише порядок збільшення часу, що витрачається на вирішення завдання розмірністю N за допомогою алгоритму А. Точні значення залежать від конкретної реалізації, тоді як О (g (N) ) є характеристикою самого алгоритму. Наприклад, якщо тимчасова асимптотична складність алгоритму дорівнює (Такий алгоритм називається квадратичним), то при збільшенні N при вирішенні задачі збільшується як квадрат N. Факт експоненційної складності алгоритму в термінах введеної символіки можна записати як. Де k - як правило, ціле число більше одиниці.
Інший вид оцінки пов'язаний з введенням "малого в": кажуть, що росте не швидше для великих N, записується. Якщо. Наприклад, очевидно, що. Інший приклад: алгоритм А є поліноміальних, якщо. Де P k (N) - деякий поліном від N ступеня k. Так, алгоритм, асимптотична складність якого дорівнює про (N log N), відноситься до поліноміальних.
Приклади асимптотических складнощів
Графіки функцій наведених в таблиці.