Обчислювальна складність: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м робот додав: sv:Komplexitetsklass |
Bunyk (обговорення | внесок) переніс таблицю з статті алгоритм. Варто було б пізніше об'єднати... |
||
Рядок 14:
Інший вид оцінки пов'язаний з введенням «малого о»: кажуть, що <math>f_A\left(N\right)</math> зростає не швидше від <math>g(N)</math> для великих N, що записується <math>f_A\left(N\right)=o\left(g\left(N\right)\right)</math>, якщо <math>\lim_{N\to\infty} f_A(N)/g(N) = 0</math>. Наприклад, очевидно, що <math>x^2=o(x^5), sin(x)=o(x)</math>. Інший приклад: алгоритм А є поліноміальним, якщо <math>f_A\left(N\right)= o\left(P_k\left(N\right)\right)</math>, де P<sub>k</sub>(N) — деякий поліном від N степеня k. Так, алгоритм, асимптотична складність якого дорівнює о(N log N), належить до поліноміальних.
== Приклади асимптотичних складностей ==
В наступній таблиці наведено поширені асимптотичні складності з коментарями.
[[Файл:Landau plots.svg|thumb|300px|Графіки функцій наведених в таблиці.]]
{| class="wikitable" border="1"
|-
! Складність
! Коментар
! Приклади
|-
| ''O''(1)
| Сталий час роботи не залежно від розміру задачі
| Очікуваний час пошуку в [[Хеш-таблиця|хеші]]
|-
| ''O''(log log ''n'')
| Дуже повільне зростання необхідного часу
| Очікуваний час роботи [[інтерполюючий пошук|інтерполюючого пошуку]] ''n'' елементів
|-
| ''O''(log ''n'')
| Логарифмічне зростання — подвоєння розміру задачі збільшує час роботи на сталу величину
| Обчислення ''x''<sup>''n''</sup>; [[двійковий пошук]] в масиві з ''n'' елементів
|-
| ''O''(''n'')
| Лінійне зростання — подвоєння розміру задачі подвоїть і необхідний час
| Додавання/віднімання чисел з ''n'' цифр; [[лінійний пошук]] в масиві з ''n'' елементів
|-
| ''O''(''n'' log ''n'')
| Лінеаритмічне зростання — подвоєння розміру задачі збільшить необхідний час трохи більше ніж вдвічі
| [[Сортування злиттям]] або [[сортування купою|купою]] ''n'' елементів; нижня границя сортування порівнянням ''n'' елементів
|-
| ''O''(''n''²)
| Квадратичне зростання — подвоєння розміру задачі вчетверо збільшує необхідний час
| Елементарні [[алгоритми сортування]]
|-
| ''O''(''n''³)
| Кубічне зростання — подвоєння розміру задачі збільшує необхідний час у вісім разів
| Звичайне множення матриць
|-
| ''O''(''c''<sup>''n''</sup>)
| Експоненціальне зростання — збільшення розміру задачі на 1 призводить до ''c''-кратного збільшення необхідного часу; подвоєння розміру задачі підносить необхідний час у квадрат
| Деякі [[задача комівояжера|задачі комівояжера]], алгоритми пошуку повним перебором
|}
== Дивіться також ==
| |||