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

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

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

Визначення

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

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

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

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

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

Дуже часто складність алгоритму задається в асимптотичному нотації 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.