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

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

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

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

Визначення

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

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

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

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

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

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

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

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

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

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

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

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

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

Приклади

Розглянемо виконання сортування включенням ${\displaystyle n}$ чисел на автоматі довільного доступу. Найкращим випадком для алгоритму є те, коли числа вже відсортовані, що займає ${\displaystyle O(n)}$ кроки для виконання завдання. Проте, вхідні дані в найгіршому випадку для алгоритму – це коли числа відсортовані у зворотному порядку і потрібно ${\displaystyle O(n^{2})}$ кроки для їх сортування; тому найгірша часова складність сортування включенням дорівнює ${\displaystyle 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. . Chapter 2.2: Analyzing algorithms, pp.25-27.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. , p.32.