Лучший, худший и средний случай
В информатике наилучший , наихудший и средний случаи данного алгоритма выражают , что использование ресурсов составляет по крайней мере , по большей части и в среднем соответственно. Обычно рассматриваемым ресурсом является время выполнения, т. е. временная сложность , но также может быть память или какой-либо другой ресурс. Наилучший случай — это функция, которая выполняет минимальное количество шагов для входных данных из n элементов. Наихудший случай — это функция, которая выполняет максимальное количество шагов для входных данных размера n. Средний случай — это функция, которая выполняет среднее количество шагов для входных данных из n элементов.
В вычислениях в реальном времени время выполнения в наихудшем случае часто вызывает особую озабоченность, поскольку важно знать, сколько времени может потребоваться в наихудшем случае, чтобы гарантировать, что алгоритм всегда будет завершаться вовремя.
Средняя производительность и производительность в худшем случае наиболее часто используются в анализе алгоритмов. Менее широко распространена производительность в лучшем случае , но она имеет применение: например, когда известны лучшие случаи отдельных задач, их можно использовать для повышения точности общего анализа в худшем случае. Специалисты по информатике используют методы вероятностного анализа , особенно ожидаемое значение , для определения ожидаемого времени выполнения.
Эти термины используются в других контекстах, например, наихудший и наилучший исход эпидемии, наихудшая температура, воздействию которой подвергается элемент электронной схемы и т. д. Если используются компоненты с указанными допусками , устройства должны быть спроектированы так, чтобы они работали должным образом при наихудшем сочетании допусков и внешних условий.
Лучшая производительность алгоритма
Термин «лучшая производительность» используется в информатике для описания поведения алгоритма в оптимальных условиях. Например, наилучший случай для простого линейного поиска в списке имеет место, когда искомый элемент является первым элементом списка.
Разработка и выбор алгоритмов редко основываются на наилучшей производительности: большинство академических и коммерческих предприятий больше заинтересованы в улучшении средней сложности и наихудшей производительности . Алгоритмы также могут быть тривиально модифицированы для достижения хорошего наилучшего времени выполнения путем жесткого кодирования решений для конечного набора входных данных, что делает эту меру почти бессмысленной. [1]
Сравнение наихудшего случая с амортизированным и средним случаем производительности
Анализ производительности в наихудшем случае и анализ производительности в среднем случае имеют некоторые сходства, но на практике обычно требуют разных инструментов и подходов.
Определить, что означает типичный ввод , сложно, и часто этот средний ввод имеет свойства, которые затрудняют его математическую характеристику (например, рассмотрим алгоритмы, разработанные для работы со строками текста). Аналогично, даже когда возможно разумное описание конкретного «среднего случая» (который, вероятно, будет применим только для некоторых применений алгоритма), они, как правило, приводят к более сложному анализу уравнений. [2]
Анализ наихудшего случая дает безопасный анализ (наихудший случай никогда не недооценивается), но он может быть излишне пессимистичным , поскольку может не быть (реалистичных) входных данных, которые бы позволили выполнить столько шагов.
В некоторых ситуациях может потребоваться использовать пессимистический анализ, чтобы гарантировать безопасность. Однако часто пессимистический анализ может быть слишком пессимистичным, поэтому анализ, который приближается к реальному значению, но может быть оптимистичным (возможно, с некоторой известной низкой вероятностью неудачи), может быть гораздо более практичным подходом. Один из современных подходов в академической теории, позволяющий преодолеть разрыв между анализом худшего и среднего случая, называется сглаженным анализом .
При анализе алгоритмов, которые часто требуют небольшого времени для завершения, но периодически требуют гораздо большего времени, амортизированный анализ может использоваться для определения наихудшего времени выполнения для (возможно бесконечной) серии операций . Эта амортизированная стоимость может быть намного ближе к средней стоимости, при этом по-прежнему обеспечивая гарантированный верхний предел времени выполнения. Так, например, онлайн-алгоритмы часто основаны на амортизированном анализе.
Анализ наихудшего случая связан со сложностью наихудшего случая . [3]
Практические последствия
Многие алгоритмы с плохой производительностью в худшем случае имеют хорошую производительность в среднем случае. Для проблем, которые мы хотим решить, это хорошо: мы можем надеяться, что конкретные случаи, которые нас интересуют, являются средними. Для криптографии это очень плохо: мы хотим, чтобы типичные случаи криптографической проблемы были сложными. Здесь методы, такие как случайная саморедуцируемость, могут использоваться для некоторых конкретных проблем, чтобы показать, что наихудший случай не сложнее среднего случая, или, что то же самое, что средний случай не проще наихудшего случая.
С другой стороны, некоторые структуры данных, такие как хэш-таблицы, имеют очень плохое поведение в худшем случае, но хорошо написанная хэш-таблица достаточного размера статистически никогда не даст худший случай; среднее число выполненных операций следует экспоненциальной кривой спада, и поэтому время выполнения операции статистически ограничено.
Примеры
Алгоритмы сортировки
| Алгоритм | Структура данных | Сложность времени:Лучшая | Временная сложность:Средняя | Временная сложность:Худшая | Сложность пространства:Худшая |
|---|---|---|---|---|---|
| Быстрая сортировка | Множество | O( n log( n )) | O( n log( n )) | О ( n2 ) | На ) |
| Сортировка слиянием | Множество | O( n log( n )) | O( n log( n )) | O( n log( n )) | На ) |
| Сортировка кучи | Множество | O( n log( n )) | O( n log( n )) | O( n log( n )) | О(1) |
| Гладкая сортировка | Множество | На ) | O( n log( n )) | O( n log( n )) | О(1) |
| Сортировка пузырьком | Множество | На ) | О ( n2 ) | О ( n2 ) | О(1) |
| Сортировка вставкой | Множество | На ) | О ( n2 ) | О ( n2 ) | О(1) |
| Сортировка по выбору | Множество | О ( n2 ) | О ( n2 ) | О ( n2 ) | О(1) |
| сортировка Bogo | Множество | На ) | О( н н !) | О(∞) | О(1) |
- Сортировка вставкой применяется к списку из n элементов, которые, как предполагается, все различны и изначально расположены в случайном порядке. В среднем половина элементов в списке A 1 ... A j меньше элемента A j +1 , а половина больше. Поэтому алгоритм сравнивает ( j + 1) -й элемент, который должен быть вставлен в среднем, с половиной уже отсортированного подсписка, так что t j = j /2. Вычисление полученного среднего времени выполнения дает квадратичную функцию размера входных данных, как и наихудшее время выполнения.
- Быстрая сортировка, примененная к списку из n элементов, снова предполагая, что все они различны и изначально расположены в случайном порядке. Этот популярный алгоритм сортировки имеет среднюю производительность O( n log( n )), что делает его очень быстрым алгоритмом на практике. Но при наихудшем входе его производительность ухудшается до O( n 2 ). Кроме того, при реализации с политикой «кратчайший первый» сложность пространства в наихудшем случае вместо этого ограничивается O(log( n )).
- Heapsort имеет время O(n), когда все элементы одинаковы. Heapify занимает O(n) времени, а затем удаление элементов из кучи занимает O(1) времени для каждого из n элементов. Время выполнения увеличивается до O(nlog(n)), если все элементы должны быть различны.
- Bogosort имеет O(n) времени, когда элементы сортируются на первой итерации. На каждой итерации все элементы проверяются на предмет их порядка. Существует n! возможных перестановок; при использовании сбалансированного генератора случайных чисел почти каждая перестановка массива получается за n! итераций. Компьютеры имеют ограниченную память, поэтому сгенерированные числа цикличны; может быть невозможно достичь каждой перестановки. В худшем случае это приводит к O(∞) времени, бесконечному циклу.
Структуры данных
| Структура данных | Сложность времени | Сложность пространства | |||||||
|---|---|---|---|---|---|---|---|---|---|
| Среднее: Индексация | Среднее: Поиск | Среднее: Вставка | Среднее: Удаление | Худшее: Индексация | Худшее: Поиск | Худшее: Вставка | Худшее: Удаление | Худший | |
| Базовый массив | О(1) | На ) | На ) | На ) | О(1) | На ) | На ) | На ) | На ) |
| Динамический массив | О(1) | На ) | На ) | — | О(1) | На ) | На ) | — | На ) |
| Куча | На ) | На ) | О(1) | О(1) | На ) | На ) | О(1) | О(1) | На ) |
| Очередь | На ) | На ) | О(1) | О(1) | На ) | На ) | О(1) | О(1) | На ) |
| Односвязный список | На ) | На ) | О(1) | О(1) | На ) | На ) | О(1) | О(1) | На ) |
| Двусвязный список | На ) | На ) | О(1) | О(1) | На ) | На ) | О(1) | О(1) | На ) |
| Пропустить список | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | На ) | На ) | На ) | На ) | O( n log ( n )) |
| Хэш-таблица | — | О(1) | О(1) | О(1) | — | На ) | На ) | На ) | На ) |
| Двоичное дерево поиска | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | На ) | На ) | На ) | На ) | На ) |
| декартово дерево | — | O(log ( n )) | O(log ( n )) | O(log ( n )) | — | На ) | На ) | На ) | На ) |
| B-дерево | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | На ) |
| Красно-черное дерево | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | На ) |
| Раскидистое дерево | — | O(log ( n )) | O(log ( n )) | O(log ( n )) | — | O(log ( n )) | O(log ( n )) | O(log ( n )) | На ) |
| Дерево АВЛ | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | На ) |
| дерево КД | O(log ( n )) | O(log ( n )) | O(log ( n )) | O(log ( n )) | На ) | На ) | На ) | На ) | На ) |
- Линейный поиск в списке из n элементов. В самом худшем случае поиск должен посетить каждый элемент один раз. Это происходит, когда искомое значение является либо последним элементом в списке, либо отсутствует в списке. Однако в среднем, предполагая, что искомое значение есть в списке и каждый элемент списка с равной вероятностью является искомым значением, поиск посещает только n /2 элементов.
Смотрите также
- Алгоритмы сортировки — область, где проводится большой объем анализа производительности различных алгоритмов.
- Структура данных поиска – любая структура данных, которая позволяет эффективно находить определенные элементы.
- Анализ схемы наихудшего случая
- Сглаженный анализ
- Интервальный конечный элемент
- Обозначение «Большое О»
Ссылки
- ^ Введение в алгоритмы (Кормен, Лейзерсон, Ривест и Стайн) 2001, Глава 2 «Начало работы». В разделе « Сложность в лучшем случае » приводится нижняя граница времени выполнения алгоритма для любых входных данных.
- ^ Шпильман, Дэниел ; Тенг, Шан-Хуа (2009), «Сглаженный анализ: попытка объяснить поведение алгоритмов на практике» (PDF) , Сообщения ACM , 52 (10), ACM: 76-84, doi :10.1145/1562764.1562785, S2CID 7904807
- ^ "Сложность наихудшего случая" (PDF) . Архивировано (PDF) из оригинала 2011-07-21 . Получено 2008-11-30 .
