Часова складність: відмінності між версіями
| [перевірена версія] | [перевірена версія] |
Вилучено вміст Додано вміст
Bluelink 1 book for Перевірність (20240201)) #IABot (v2.0.9.5) (GreenC bot |
Tolsai (обговорення | внесок) Функція пропозицій посилань: додано 2 посилання. |
||
Рядок 79:
Кажуть, що алгоритм виконується за лінійний час або час {{math|''O''(''n'')}}, коли його складність дорівнює {{math|''O''(''n'')}}. По простому, це означає, що час виконання зростає щонайбільше лінійно від кількості вхідних даних. Більш точно, це означає, що існує константа {{mvar|c}}, така, що час виконання буде щонайбільше {{math|''cn''}}, коли розмір вхідних даних {{mvar|n}}. Наприклад, час виконання процедури, яка знаходить суму всіх елементів списку, буде пропорційною довжині списку за умови, що час виконання операції додавання є сталим, або, принаймні, обмежений сталою.
Лінійний час є найкращим за часовою складністю у ситуації, коли алгоритм послідовно читає вхідні дані. Тому, так багато досліджень на виявлення алгоритмів, які виконуються за лінійний час або, принаймні, майже за лінійний час. Ці дослідження включають як програмні, так і апаратні методи. Для досягнення цього є декілька апаратних методів заснованих на [[Паралельні обчислення|паралельних обчисленнях]]. Прикладом цього є [[асоціативна пам'ять]]. Концепція лінійного часу використовується в [[Алгоритм пошуку|алгоритмах пошуку]] збігів у текстах, зокрема, в [[Алгоритм Бойера Мура|алгоритмі Боєра Мура]] та {{Нп|Алгоритм Укконена|алгоритмі Укконена||Ukkonen's algorithm}}.
== Доквадратичний час ==
Рядок 91:
Деякі приклади алгоритмів поліноміального часу:
* Алгоритм [[сортування вибором]] ''n'' цілих чисел виконує <math>An^2</math> операцій, де ''A'' — константа. Отже, він виконується за час <math>O(n^2)</math> і є поліноміальним алгоритмом.
* Всі основні арифметичні операції (додавання, [[віднімання]], множення, ділення та порівняння) можна виконати за поліноміальний час.
* [[Парування (теорія графів)|Максимальне парування]] в [[Граф (математика)|графах]] можна знайти за поліноміальний час.
| |||