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

 

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