Поняття складності алгоритмів

V. КЛАСИ СКЛАДНОСТІ P I NP

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

Під складністю алгоритму розуміють одну з асимптотичних оцінок функції складності алгоритму (зазвичай використовується О-оцінка). Наприклад, говорять: "Складність алгоритму А є О(n³).

По складності алгоритми ділять на категорії. Приклади деяких категорій складності алгоритмів :

- алгоритми поліноміальної складності, F(n) = O(n^p);

- алгоритми експоненціальної складності, F(n) = O(e^{a n});

- алгоритми факторіальної складності, F(n) = O(n!).

Алгоритми, що мають поліноміальну функцію складності, математики називають ефективними.

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

Трудомісткість алгоритмів по-різному залежить від вхідних даних. Для деяких алгоритмів трудомісткість залежить тільки від об'єму даних, для інших алгоритмів — від значень даних, в деяких випадках порядок вступу даних може впливати на трудомісткість. Трудомісткість багатьох алгоритмів може в тій чи іншій мірі залежати від усіх перелічених вище чинників.

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

Основною оцінкою функції складності алгоритму f(n) є оцінка Θ. Тут n — величина об'єму даних або довжина входу. Ми говоримо, що оцінка складності алгоритму f(n)=Θ(g(n)), якщо при g>0 при n>0 існують позитивні с₁ с₂, n₀, такі, що при n>n₀, інакше кажучи, можна знайти такі с₁ і c₂, що при досить великих n, f(n) буде між c₁g(n) і c₂g(n).

У такому випадку говорять ще, що функція g(n) є асимптотично точною оцінкою функції f(n), оскільки за визначенням функція f(n) не відрізняється від функції g(n) з точністю до постійного множника. Наприклад, для методу сортування heapsort оцінка трудомісткості складає

Важливо розуміти, що Θ(g(n)) є не функцією, а множиною функцій, що описують ріст f(n) з точністю до постійного множника.

Θ дає одночасно верхню і нижню оцінки росту функції. Часто необхідно розглядати ці оцінки окремо. Оцінка O представляет собою верхню асимптотичну оцінку трудомісткості алгоритму. Ми говоримо, що f(n)=O(g(n)) якщо

Інакше кажучи, запис f(n)=O(g(n)) означає, що f(n) належить класу функцій, які ростуть не швидше, ніж функція g(n) з точністю до постійного множника.

Оцінка Ω задає нижню асимптотичну оцінку росту функції f(n) і визначає клас функцій, які ростуть не повільніше, ніж g(n)з точністю до постійного множника f(n)=Ω(g(n)). якщо

Наприклад, запис f(n)=O(n log n) означає клас функцій, які ростуть не повільніше, ніж g(n)=n log n, в цей клас потрапляють усі поліноми з мірою більшої одиниці, так само як і усі степенні функції з основою більшою одиниці. Рівність f(n)=Θ(g(n)) виконується тоді і тільки тоді, коли f(n)=O(g(n)) i f(n)=Ω(g(n)).

Асимптотичний аналіз алгоритмів має не лише практичне, але і теоретичне значення. Так, наприклад, доведено, що усі алгоритми сортування, засновані на попарному порівнянні елементів, відсортують n елементів за час, не менший Ω(n log n).