Часова складність алгоритму в комп'ютерних науках є обчислювальною складністюалгоритму, яка описує час потрібний для виконання алгоритму. Вона зазвичай визначається шляхом підрахунку кількості елементарних операцій, виконуваних алгоритмом, при цьому вважають, що кожна елементарна операція виконується за фіксовану кількість часу. Таким чином, кількість часу і кількість елементарних операцій, необхідних для виконання алгоритму, відрізняються постійним множником.
Оскільки час роботи алгоритму може відрізнятися на вхідних даних одного розміру, то зазвичай розглядається найгірший випадок складності, який відповідає максимальному часу, необхідного для виконання при вхідних даних заданого розміру. Менш поширеною і, як правило, явно вказаною є складність алгоритму у середньому[en], яка є середньою величиною часу на вхідні дані даного розміру (це має сенс, оскільки існує лише скінченне число можливих вхідних даних даного розміру). В обох випадках часова складність алгоритму є функцією від розміру вхідних даних.[1] Оскільки ці функції, як правило, важко точно розрахувати, а час роботи у випадку невеликого розміру вхідних даних, не завжди прогнозований, тому зазвичай оцінюють поведінку складності при збільшенні розміру вхідних даних, тобто асимптотичну поведінку складності алгоритму. Це пояснює, чому зазвичай часову складність часто описують за допомогою нотації великого О, зазвичай і т. д., де n відповідає розміру вхідних даних в одиницях вимірювання або в бітах, які потрібні для їх представлення.
Алгоритмічна складність класифікується відповідно до типу функції, яка її описує в нотації великого О. Наприклад, алгоритм зі складністю є алгоритмом лінійної складності, а алгоритм зі складністю для деякої константи є алгоритмом поліноміальної складності.
Кажуть, що алгоритм виконується за сталий час (записується як 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(n2).
Наприклад, простий, заснований на порівнянні алгоритм сортування буде квадратичним (наприклад, сортування включенням), але більш розвинуті алгоритмі можуть мати доквадратичний час виконання (наприклад, сортування Шелла). Немає загальних алгоритмів, які виконуються за лінійний час, проте зміна квадратичного часу на доквадратичний дуже важлива з практичної точки зору.
Поліноміальний час
Кажуть, що алгоритм виконується за поліноміальний час, якщо верхнею межею часу виконання є поліноміальний вираз від розміру вхідних даних алгоритму, тобто, від деякої додатної константи k.[1][4]Задачі, для яких існує алгоритм розв'язання, що виконується за поліноміальний час, належать до класу складності P, що є центральним питанням в теорії складності обчислень. Теза Кобгама[en] стверджує, що поліноміальний час є синонімом «здійсненний», «ефективний» або «швидкий».[5]
Деякі приклади алгоритмів поліноміального часу:
Алгоритм сортування виборомn цілих чисел виконує операцій, де A — константа. Отже, він виконується за час і є поліноміальним алгоритмом.
Всі основні арифметичні операції (додавання, віднімання, множення, ділення та порівняння) можна виконати за поліноміальний час.
↑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.
↑Cobham, Alan (1965). The intrinsic computational difficulty of functions. Proc. Logic, Methodology, and Philosophy of Science II. North Holland.
В іншому мовному розділі є повніша стаття Time complexity(англ.). Ви можете допомогти, розширивши поточну статтю за допомогою перекладу з англійської. (листопад 2023)
Перекладач повинен розуміти, що відповідальність за кінцевий вміст статті у Вікіпедії несе саме автор редагувань. Онлайн-переклад надається лише як корисний інструмент перегляду вмісту зрозумілою мовою. Не використовуйте невичитаний і невідкоригований машинний переклад у статтях української Вікіпедії!
Машинний переклад Google є корисною відправною точкою для перекладу, але перекладачам необхідно виправляти помилки та підтверджувати точність перекладу, а не просто скопіювати машинний переклад до української Вікіпедії.
Не перекладайте текст, який видається недостовірним або неякісним. Якщо можливо, перевірте текст за посиланнями, поданими в іншомовній статті.