Складність алгоритмів

Час роботи будь-якого алгоритму залежить від кількості вхідних даних. Так при роботі алгоритму сортування час залежить від розміру вхідного масиву. В загальному вивчають залежність часу роботи алгоритму від розміру входу. В одних задачах розмір входу це кількість елементів на вході (задача сортування, перетворення Фур‘є). В інших випадках розмір входу це загальна кількість бітів, що необхідні для представлення всіх вхідних даних.

Часом роботи алгоритму називається число елементарних кроків, які він виконує [3]. Вважається, що один рядок псевдокоду вимагає не більше ніж фіксованого числа операцій.

Розрізняють також виклик функції, на який іде фіксована кількість операцій та виконання функції, яке може бути довгим. Так для алгоритму пошуку максимального за значенням числа в масиві розміром n необхідно виконати n кроків. Тоді час роботи такого алгоритму позначимо Т(n). Для кожного алгоритму проводиться оцінка кожної операції, скільки разів ця операція виконується. Всі оцінки додаються і виводиться залежність часу роботи алгоритму від розміру входу.

Якщо алгоритм призначений для обробки рівних за об‘ємом даних, тривалість його роботи щораз залишається незмінною й складність алгоритму є постійною.Час роботи алгоритму обробки яких-небудь масивів даних залежить від розмірів цих масивів. Час роботи алгоритму, що виконує тільки операції читання й занесення даних в оперативну пам'ять, визначається формулою an+b, де а - час, необхідний для читання й занесення в пам‘ять однієї інформаційної одиниці, і b - час, затрачуваний на виконання допоміжних функцій. Оскільки ця формула виражає лінійну залежність від n, складність відповідного алгоритму називають лінійною.

Якщо алгоритм передбачає виконання двох незалежних циклів, перший від 1 до k, і другий від 1 до t, то загальна кількість кроків буде k+t, а час роботи Т(k+t). Якщо алгоритм передбачає виконання двох вкладених циклів, від 1 до k і від 1 до t, то загальна кількість кроків буде k*t, а час роботи Т(k*t). Це є лінійна функція. І вона є найбільш сприятливою для оцінки швидкодії алгоритму. Чим більша степінь складності алгоритму в залежності від розміру входу (n², n³, nⁿ …) тим ефективність алгоритму нижча.

Час роботи алгоритму також залежить від подачі вхідних даних. Так для алгоритму сортування «бульбашкою» суттєво як розміщені елементи вхідного масиву. Якщо вони частково відсортовані, то вихід за прапорцем відбудеться швидше. Якщо елементи стоять в різнобій, то алгоритм відпрацює всі цикли повністю.

Складність можна оцінити як стосовно задачі, так і стосовно алгоритму. Оцінками часу роботи алгоритму є максимальний, мінімальний і середній час його виконання. Залежно від використовуваних евристик ці оцінки можуть збігатися або не збігатися.

Складність задачі повинна оцінюватися за реалізаціями правильних алгоритмів. Вона, являє собою верхню межу для часу роботи алгоритму. Але часто можна знайти також і нижню межу. Очевидно, що для виконання якого-небудь виду обробки n елементів потрібен час, принаймні пропорційний n.

Час роботи в гіршому випадку є більш цікавим для дослідження ефективності алгоритму, оскільки:

1) це гарантує, що виконання алгоритму закінчиться за деякий час, незалежно від розміру входу;

2) на практиці «погані» входи трапляються частіше;

3) час роботи в середньому є достатньо близьким до часу роботи в гіршому випадку.

Розглянемо три позначення асимптотики росту часу роботи алгоритму].

Q - позначення (тета)

Наприклад, якщо час роботи Т(n) деякого алгоритму становить залежність n² від розміру входу, то знайдуться такі константи c₁, с₂ > 0 і таке число n₀ що с₁n²≤ Т(n) ≤ с₂ n² при всіх n≥0. Взагалі, якщо g(n) - деяка функція, то запис f(n) = Q (g(n)) (тета) означає, що знайдуться такі c₁, с₂ > 0 і таке n₀, що 0 ≤c₁g(n) ≤ f(n) ≤ c₂g(n) для всіх n > n₀. Тобто складність алгоритму геометрично розміщена в межах умовної смуги між функціями c₁g(n) і c₂g(n) (рис.2.1.а).

О- позначення (о)

Запис f(n) = Q (g(n)) включає дві оцінки: верхню і нижню. Їх можна розділити. Говорять, що f(n) = О(g(n)), якщо знайдеться така константа c > 0 і таке число n₀, що 0 < f(n) ≤ сg(n) для всіх n ≥ n₀ – верхня оцінка, тобто складність алгоритму не перевищує деякої функції сg(n) і геометрично знаходиться нижче її графіку (рис.2.1.б).

Ω – позначення (омега)

Говорять, що f(n) = Ω(g(n)), якщо знайдеться така константа c > 0 і таке число n₀, що 0 ≤ сg(n) ≤ f(n) для всіх n ≥ n₀ – нижня оцінка, тобто складністьалгоритму не менша деякої функції сg(n) і геометрично знаходиться вище її графіку (рис.2.1.в).

а) для f(n) = Q (g(n)); б) для f(n) = О(g(n)); в) для f(n) = Ω(g(n)).

Введені позначення володіють властивостями транзитивності, рефлективності та симетричності.

Транзитивність:

f(n) = Q (g(n)) і g(n) = Q (h(n)) то f(n) = Q (h(n))

f(n) = O(g(n)) і g(n) = O (h(n)) то f(n) = O (h(n))

f(n) = Ω (g(n)) і g(n) = Ω (h(n)) то f(n) = Ω (h(n))

Рефлексивність:

f(n) = Q (f(n)), f(n) = O(f(n)), f(n) = Ω (f(n)).

Симетричність:

f(n) = Q (g(n)) якщо і тільки якщо g(n) = Q (f(n)).

Наприклад, алгоритм зчитування й занесення в пам‘ять множини даних має оцінку О(n). Алгоритм двійкового пошуку в таблиці з упорядкованими елементами оцінюється як О (log₂ n). Просте обмінне сортування має оцінку О (n²), a множення матриць - О (n³). Коли говорять, що складність сортування рівна О (n²), під цим мається на увазі, що сортування інформації буде виконано в найкращому випадку за час, пропорційний n².

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

У таблиці 2.1 показана залежність різних видів складності алгоритмів від зростання n. Логарифмічна залежність більш прийнятна, ніж лінійна, а лінійна залежність переважніше поліноміальної й експонентної [1].

Таблиця 2.1.

Складність алгоритмів

n	О (log2n)	O(n)	О (n1og2n)	O(n2)	O(2n)	О (n!)	О (nn)
	2,3219 3,3219 4,3219 4,9069 6,6439		11,6069 33,2193 86,4386 147,2067 664,3856		1,024 106 109 1030	3,6*106 2,4*1018 2,6*1032 1051	3,125 1010 1026 2*1044 10200