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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

Визначення[ред.ред. код]

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

Виявляється, що між цими класами алгоритмів є істотна різниця: при великих розмірностях задач (які, зазвичай, найцікавіші на практиці), поліноміальні алгоритми можуть бути виконані на сучасних комп'ютерах, тоді як експоненціальні алгоритми для практичних розмірностей задач, як правило, не можуть виконатися повністю. Зазвичай розв'язання задач, що породжують експоненціальні алгоритми, пов'язаний з повним перебором всіх можливих варіантів, і зважаючи на практичну неможливість реалізації такої стратегії, для їх розв'язання розробляються інші підходи.

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

Поліноміальні алгоритми також можуть істотно розрізнятися залежно від степеня полінома, що апроксимує залежність f_{A}\left(N\right). Розглянемо оцінювання часової складності алгоритму. Така оцінка проводиться із застосуванням відношення O («велике О»): кажуть, що f_{A}\left(N\right) зростає як g\left(N\right) для великих N і записується це як f_{A}\left(N\right)=O\left(g\left(N\right)\right). Якщо існує позитивна константа Const>0, така, що \lim_{N\to\infty} f_A(N)/g(N) = Const, то оцінка О(g(N)) називається асимптотичною часовою складністю алгоритму.

Оцінка О(g(N)) для функції f_A\left(N\right) застосовується, коли точне значення f_A\left(N\right) невідоме, а відомо лише порядок зростання часу, затрачуваного на розв'язання задачі розмірністю N за допомогою алгоритму А. Точні значення f_A\left(N\right) залежать від конкретної реалізації, тоді як О(g(N)) є характеристикою самого алгоритму. Наприклад, якщо часова асимптотична складність алгоритму дорівнює O(N^2) (такий алгоритм називається квадратичним), то при збільшенні N час розв'язання задачі збільшується як квадрат N. Факт експоненціальної складності алгоритму в термінах введеної символіки можна записати як f_A\left(N\right)=O\left(k^N\right), де k — як правило, ціле число більше за одиницю.

Інший вид оцінки пов'язаний з введенням «малого о»: кажуть, що f_A\left(N\right) зростає не швидше від g(N) для великих N, що записується f_A\left(N\right)=o\left(g\left(N\right)\right), якщо \lim_{N\to\infty} f_A(N)/g(N) = 0. Наприклад, очевидно, що x^2=o(x^5), sin(x)=o(x). Інший приклад: алгоритм А є поліноміальним, якщо f_A\left(N\right)= o\left(P_k\left(N\right)\right), де Pk(N) — деякий поліном від N степеня k. Так, алгоритм, асимптотична складність якого дорівнює о(N log N), належить до поліноміальних.

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

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

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


Див. також[ред.ред. код]

Література[ред.ред. код]

  • Джон Хопкрофт, Раджив Мотвани, Джеффри Ульман Введение в теорию автоматов, языков и вычислений = Introduction to Automata Theory, Languages, and Computation. — М.: «Вильямс», 2002. — С. 528.


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