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

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

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

Визначення

Дано модель обчислення та алгоритм , що зупиняється на кожного вході , відображення  називається часовою складністю , якщо для кожного вхідного рядка ,  зупиняється через рівно  кроки.

Оскільки ми, як правило, зацікавлені в залежності часової складності від різних довжин вхідних даних, використовуючи термінологію, часову складність іноді називають відображенням , що визначається максимальною складністю

:

входів  з довжиною або розміром .

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

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

Дуже часто складність  алгоритму  задається в асимптотичному нотації Big-O, що дає його швидкість росту у вигляді  з певною дійсною функцією порівняння  і значення:
* Існує позитивне дійсне число  і натуральне число  таке, що

:

Досить часто формулюванням є:
* «Алгоритм  має найгіршу складність .»
або навіть лише:
* «Алгоритм  має складність .»

Приклади

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

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

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

Література

* 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.

