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