Часова складність

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

Оскільки час роботи алгоритму може відрізнятися на вхідних даних одного розміру, то зазвичай розглядається найгірший випадок складності, який відповідає максимальному часу, необхідного для виконання при вхідних даних заданого розміру. Менш поширеною і, як правило, явно вказаною є складність алгоритму у середньому^[en], яка є середньою величиною часу на вхідні дані даного розміру (це має сенс, оскільки існує лише скінченне число можливих вхідних даних даного розміру). В обох випадках часова складність алгоритму є функцією від розміру вхідних даних.^[1] Оскільки ці функції, як правило, важко точно розрахувати, а час роботи у випадку невеликого розміру вхідних даних, не завжди прогнозований, тому зазвичай оцінюють поведінку складності при збільшенні розміру вхідних даних, тобто асимптотичну поведінку складності алгоритму. Це пояснює, чому зазвичай часову складність часто описують за допомогою нотації великого О, зазвичай $O(n),$ $O(n\log n),$ $O(n^{\alpha }),$ $O(2^{n}),$ і т. д., де $n$ відповідає розміру вхідних даних в одиницях вимірювання або в бітах, які потрібні для їх представлення.

Алгоритмічна складність класифікується відповідно до типу функції, яка її описує в нотації великого О. Наприклад, алгоритм зі складністю $O(n)$ є алгоритмом лінійної складності, а алгоритм зі складністю $O(n^{\alpha })$ для деякої константи $\alpha >1$ є алгоритмом поліноміальної складності.

Таблиця типових часових складностей

У таблиці наведено деякі поширені класи часових складностей. У таблиці, для зручності через poly(x) = x^O(1) позначаємо поліном від x.

Назва	Обчислювальна складність	Час виконання (T(n))	Приклади часу виконання	Приклади алгоритмів
сталий час		O(1)	10	Визначенно парності числа (у двійковому запису)
обернена Функція Акермана від часу		O(α(n))		Амортизаційний аналіз на одну операцію з використанням неперетинних множин
повторний логарифмічний час		O(log* n)		Розподілені розфарбовування циклів
двічі логарифмічний		O(log log n)		Час амортизації на одну операцію при використанні обмеженої черги з пріоритетом^[2]
логарифмічний час	DLOGTIME	O(log n)	log n, log(n²)	Двійковий пошук
полілогарифмічний час		poly(log n)	(log n)²
дробовий степінь		$O (n c)$ where $0 < c < 1$	n^1/2, n^2/3	Пошук у К-вимірному дереві
сублінійний час		O(n/log n*)	n/(log n), n/(log log n)	Пошук усіх простих чисел, менших заданого n, решетом Аткіна
лінійний час		O(n)	n	Пошук найбільшого або найменшого елементу невпорядкованого масиву
«n log зірочка n» час		O(n log* n)	n log log n	Решето Ератосфена Алгоритм Зейделя^[en] тріангуляції многокутника
квазілінійний час		O(n log n)	n log n, log n!	Найшвидше можливе сортування порівняннями; Швидке перетворення Фур'є.
квадратичний час		O(n²)	n²	Сортування бульбашкою; Сортування включенням
кубічний час		O(n³)	n³	Безпосереднє множення двох матриць розміру n×n. Обчислення часткової кореляції.
поліноміальний час	P	2^O(log n) = poly(n)	n, n log n, n¹⁰	Алгоритм Кармаркара для лінійного програмування; Тест простоти AKS
квазіполіноміальний час	QP	2^poly(log n)	n^log log n, n^log n	Відомий O(log² n)-апроксимаційний алгоритм для пошуку дерева Штейнера.
субекспоненціальний час (перше визначення)	SUBEXP	O(2^{n^ε}) для всіх ε > 0	O(2^{log n^{log log n}})	Якщо прийняти теоретичні гіпотези, BPP міститься в SUBEXP.^[3]
субекспоненціальний час (друге визначення)		2^o(n)	2^{n^1/3}	Відомий алгоритм розкладання числа на множники та задача ізоморфізму графів^[en]
експоненціальний час (з лінійною експонентою)	E	2^O(n)	1.1ⁿ, 10ⁿ	Вирішення задачі комівояжера за допомогою динамічного програмування
експоненціальний час	EXPTIME	2^poly(n)	2ⁿ, 2^n²	Вирішення задачі перемноження матриць^[en] повним перебором
факторіальний час		O(n!)	n!	Вирішення задачі комівояжера повним перебором
double exponential time	2-EXPTIME	2^{2^poly(n)}	2^2ⁿ	Перевірка на істину твердження в арифметиці Пресбургера

Сталий час

Кажуть, що алгоритм виконується за сталий час (записується як O(1) час), якщо значення T(n) обмежене величиною, яка не залежить від розміру вхідних даних. Наприклад, доступ до одного елемента у масиві займає сталий час, коли потрібна лише одна операція для знаходження його місця розташування. Аналогічним чином, знаходимо мінімальне значення в масиві, відсортованому у порядку зростання; це буде перший елемент. Проте, пошук мінімального елемента у невпорядкованому масиві не буде операцією, яка виконується за сталий час, бо вона потребує отримання кожного елемента масива для визначення найменшого значення. Отже, цю операцію можна виконати за лінійний час O(n). Якщо ж кількість елементів відома заздалегідь і не змінюється, тоді про такий алгоритм ще можна сказати, що він виконується за сталий час.

Незважаючи на назву «сталий час», час роботи не повинен бути незалежним від розміру вхідних даних, але верхня межа часу роботи повинна бути обмежена незалежно від розміру вхідних даних. Наприклад, завдання «якщо потрібно, то обміняти значення a та b, так, щоб a ≤ b» виконується за сталий час, хоча і залежить від того, чи відразу виконується умова a ≤ b. Це тому, що є стала t, така, що потрібний час завжди не перевищує t.

Далі наведено приклад фрагменту коду, який виконується за сталий час:

int index = 5;
int item = list[index];
if (умова) then
   виконати деяку операцію, яка потребує сталого часу
else
   виконати деяку операцію, яка потребує сталого часу
for i = 1 to 100
   for j = 1 to 200
      виконати деяку операцію, яка потребує сталого часу

Якщо T(n) є O(будь-яка стала), то це еквівалентно T(n) дорівнює O(1).

Лінійний час

Кажуть, що алгоритм виконується за лінійний час або час $O (n)$ , коли його складність дорівнює $O (n)$ . По простому, це означає, що час виконання зростає щонайбільше лінійно від кількості вхідних даних. Більш точно, це означає, що існує константа $c$ , така, що час виконання буде щонайбільше $cn$ , коли розмір вхідних даних $n$ . Наприклад, час виконання процедури, яка знаходить суму всіх елементів списку, буде пропорційною довжині списку за умови, що час виконання операції додавання є сталим, або, принаймні, обмежений сталою.

Лінійний час є найкращим за часовою складністю у ситуації, коли алгоритм послідовно читає вхідні дані. Тому, так багато досліджень на виявлення алгоритмів, які виконуються за лінійний час або, принаймні, майже за лінійний час. Ці дослідження включають як програмні, так і апаратні методи. Для досягнення цього є декілька апаратних методів заснованих на паралельних обчисленнях. Прикладом цього є асоціативна пам'ять. Концепція лінійного часу використовується в алгоритмах пошуку збігів у текстах, зокрема, в алгоритмі Боєра Мура та алгоритмі Укконена^[en].

Доквадратичний час

Алгоритм має доквадратичний час, коли час виконання T(n) = o(n²).

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

Поліноміальний час

Кажуть, що алгоритм виконується за поліноміальний час, якщо верхнею межею часу виконання є поліноміальний вираз від розміру вхідних даних алгоритму, тобто, від деякої додатної константи k.^[1]^[4] Задачі, для яких існує алгоритм розв'язання, що виконується за поліноміальний час, належать до класу складності P, що є центральним питанням в теорії складності обчислень. Теза Кобгама^[en] стверджує, що поліноміальний час є синонімом «здійсненний», «ефективний» або «швидкий».^[5]

Деякі приклади алгоритмів поліноміального часу:

Алгоритм сортування вибором n цілих чисел виконує $An^{2}$ операцій, де A — константа. Отже, він виконується за час $O(n^{2})$ і є поліноміальним алгоритмом.
Всі основні арифметичні операції (додавання, віднімання, множення, ділення та порівняння) можна виконати за поліноміальний час.
Максимальне парування в графах можна знайти за поліноміальний час.

Див. також

L-нотація
DSPACE^[en] - просторова складність

Примітки

↑ ^а ^б Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.
↑ Mehlhorn, Kurt; Naher, Stefan (1990). Bounded ordered dictionaries in O(log log N) time and O(n) space. Information Processing Letters. 35 (4): 183—189. doi:10.1016/0020-0190(90)90022-P.
↑ Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity. Berlin, New York: Springer-Verlag. 3 (4): 307—318. doi:10.1007/BF01275486.
↑ Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.
↑ Cobham, Alan (1965). The intrinsic computational difficulty of functions. Proc. Logic, Methodology, and Philosophy of Science II. North Holland.

[Sipser-1] а ^б Sipser, Michael (2006). Introduction to the Theory of Computation. Course Technology Inc. ISBN 0-619-21764-2.

[2] Mehlhorn, Kurt; Naher, Stefan (1990). Bounded ordered dictionaries in O(log log N) time and O(n) space. Information Processing Letters. 35 (4): 183—189. doi:10.1016/0020-0190(90)90022-P.

[bpp-3] Babai, László; Fortnow, Lance; Nisan, N.; Wigderson, Avi (1993). BPP has subexponential time simulations unless EXPTIME has publishable proofs. Computational Complexity. Berlin, New York: Springer-Verlag. 3 (4): 307—318. doi:10.1007/BF01275486.

[4] Papadimitriou, Christos H. (1994). Computational complexity. Reading, Mass.: Addison-Wesley. ISBN 0-201-53082-1.

[5] Cobham, Alan (1965). The intrinsic computational difficulty of functions. Proc. Logic, Methodology, and Philosophy of Science II. North Holland.

[1]

[2]

[3]

[4]

[5]