В Інформатиці (зокрема теорії складності обчислень), складність найгіршого випадку вимірює ресурси (наприклад, час виконання, пам'ять), які алгоритм потребує введення довільного розміру (зазвичай позначається як n в асимптотичному позначенні). Вона дає верхню межу ресурсів, необхідних алгоритму.
У випадку часу виконання, найгірший випадок часової складності вказує на найдовший час виконання алгоритму з заданим будь-яким введенням розміру n, і тим самим гарантує, що алгоритм завершиться у вказаний період часу. Порядок зростання (наприклад, лінійний, [en]) найгіршого випадку складності зазвичай використовується для порівняння ефективності двох алгоритмів.
Складність алгоритму в найгіршому випадку слід порівняти його [en], що є середнім показником кількості ресурсів, яку алгоритм використовує для випадкового введення.
Визначення
Дано модель обчислення та алгоритм , що зупиняється на кожного вході , відображення називається часовою складністю , якщо для кожного вхідного рядка , зупиняється через рівно кроки.
Оскільки ми, як правило, зацікавлені в залежності часової складності від різних довжин вхідних даних, використовуючи термінологію, часову складність іноді називають відображенням , що визначається максимальною складністю
входів з довжиною або розміром .
Подібні визначення можна дати для складності простору, випадкової складності, тощо.
Способи мовлення
Дуже часто складність алгоритму задається в асимптотичному нотації 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.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет