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