Обчислювальна складність: відмінності між версіями

▲Складність обчислювальних процесів — це поняття теорії складності обчислень

▲Нехай А - алгоритм розв’язання деякого класу задач, а <math>N</math> - розмірність окремої задачі цього класу. <math>N</math> може бути, наприклад, розмірністю оброблюваного масиву, числом вершин оброблюваного графа і т.д. Позначимо <math>f_{A}(N)</math> функцію, що дає верхню межу максимального числа основних операцій (додавання, множення і т. д.), які повинен виконати алгоритм А, розв’язуючи задачу розмірності <math>N</math>. Говоритимемо, що алгоритм А поліноміальний, якщо <math>f_А(N)</math> зростає не швидше, ніж деякий поліном від <math>N</math>. В противному випадку А - експоненціальний алгоритм. Виявляється, що між цими класами алгоритмів є істотна різниця: при великих розмірностях задач (які, зазвичай, найцікавіші на практиці), поліноміальні алгоритми можуть бути виконані на сучасних комп'ютерах, тоді як експоненціальні алгоритми для практичних размірностей задач, як правило, не можуть виконатися повністю. Зазвичай розв’язання задач, що породжують експоненціальні алгоритми, пов'язаний з повним перебором всіх можливих варіантів, і зважаючи на практичну неможливість реалізації такої стратегії, для їх розв’язання розробляються інші підходи. Наприклад, якщо навіть існує експоненціальний алгоритм для знаходження оптимального розв’язку деякої задачі, то на практиці застосовуються інші, ефективніші поліноміальні алгоритми для знаходження не обов'язково оптимального, а лише прийнятного розв’язку (наближеного до оптимального). Але навіть якщо задача допускає розв’язання за допомогою поліноміального алгоритму, його можна побудувати лише після глибокого вникання в суть поставленої задачі.

▲Поліноміальні алгоритми також можуть істотно розрізнятися залежно від степеня полінома, що апроксимує залежність <math>f_{А}(N)</math>. Розглянемо оцінювання часової складності алгоритму. Така оцінка проводиться із застосуванням відношення <math>О</math> (“велике О”): кажуть, що <math>f_А(N)</math> зростає як <math>g(N)</math> для великих N і записується це як <math>f_А(N)=O(g(N))</math>. Якщо існує позитивна константа Сonst>0, така, що <math>\lim_{N\arrow\infty} f_А(N)/g(N) = Const</math>, то оцінка О(g(N)) називається асимптотичною часовою складністю алгоритму. Оцінка О(g(N)) для функції <math>f_А(N)</math> застосовується, коли точне значення <math>f_А(N)</math> невідоме, а відомо лише порядок зростання часу, затрачуваного на розв’язання задачі розмірністю N за допомогою алгоритму А. Точні значення <math>f_А(N)</math> залежать від конкретної реалізації, тоді як О(g(N)) є характеристикою самого алгоритму. Наприклад, якщо тимчасова асимптотична складність алгоритму дорівнює <math>О(N^2)</math> (такий алгоритм називається квадратичним), то при збільшенні N час розв’язання задачі збільшується як квадрат N. Факт експоненціальної складності алгоритму в термінах введеної символіки можна записати як <math>f_А(N)=O(k^N)</math>, де k — як правило ціле число більше за одиницю.