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

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

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

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

Визначення

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

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

$t_{𝖠}(n):=\underset{s\in \{0,1{\}}^n}{\max }{t}_{𝖠}(s)$

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

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

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

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

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

$|t_{𝖠}(n)|\le Mg(n)\mathrm{\forall }n\ge n_0.$

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

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

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

• «Алгоритм $𝖠$ має складність $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. Chapter 2.2: Analyzing algorithms, pp.25-27.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. Шаблон:ISBN, p.32.