Найгірший випадок складності

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

У випадку часу виконання, найгірший випадок часової складності вказує на найдовший час виконання алгоритму з заданим будь-яким введенням розміру n, і тим самим гарантує, що алгоритм завершиться у вказаний період часу. Порядок зростання (наприклад, лінійний, логарифмічний) найгіршого випадку складності зазвичай використовується для порівняння ефективності двох алгоритмів.

Складність алгоритму в найгіршому випадку слід порівняти його середньою складністю, що є середнім показником кількості ресурсів, яку алгоритм використовує для випадкового введення.

Визначення

Дано модель обчислення та алгоритм ${\mathsf {A}}$, що зупиняється на кожного вході $s$, відображення $t_{\mathsf {A}}\colon \{0,1\}^{\star }\to \mathbb {N}$ називається часовою складністю ${\mathsf {A}}$, якщо для кожного вхідного рядка $s$, ${\mathsf {A}}$ зупиняється через рівно $t_{\mathsf {A}}(s)$ кроки.

Оскільки ми, як правило, зацікавлені в залежності часової складності від різних довжин вхідних даних, використовуючи термінологію, часову складність іноді називають відображенням $t_{\mathsf {A}}\colon \mathbb {N} \to \mathbb {N}$, що визначається максимальною складністю

$t_{\mathsf {A}}(n):=\max _{s\in \{0,1\}^{n}}t_{\mathsf {A}}(s)$

входів $s$ з довжиною або розміром $\leq n$.

Подібні визначення можна дати для складності простору, випадкової складності, тощо.

Способи мовлення

Дуже часто складність $t_{\mathsf {A}}$ алгоритму ${\mathsf {A}}$ задається в асимптотичному нотації Big-O, що дає його швидкість росту у вигляді $t_{\mathsf {A}}=O(g(n))$ з певною дійсною функцією порівняння $g(n)$ і значення:

• Існує позитивне дійсне число $M$ і натуральне число $n_{0}$ таке, що

$|t_{\mathsf {A}}(n)|\leq Mg(n)\quad \forall \quad n\geq n_{0}.$

Досить часто формулюванням є:

• «Алгоритм ${\mathsf {A}}$ має найгіршу складність $O(g(n))$.»

або навіть лише:

• «Алгоритм ${\mathsf {A}}$ має складність $O(g(n))$.»

Приклади

Розглянемо виконання сортування включенням $n$ чисел на автоматі довільного доступу. Найкращим випадком для алгоритму є те, коли числа вже відсортовані, що займає $O(n)$ кроки для виконання завдання. Проте, вхідні дані в найгіршому випадку для алгоритму – це коли числа відсортовані у зворотному порядку і потрібно $O(n^{2})$ кроки для їх сортування; тому найгірша часова складність сортування включенням дорівнює $O(n^{2})$.

Дивіться також

• Аналіз алгоритмів

Література

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 2.2: Analyzing algorithms, pp.25-27.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. ISBN 0-521-88473-X, p.32.