В информатике наилучший , наихудший и средний случаи данного алгоритма выражают , что использование ресурсов составляет по крайней мере , по большей части и в среднем соответственно. Обычно рассматриваемым ресурсом является время выполнения, т. е. временная сложность , но также может быть память или какой-либо другой ресурс. Наилучший случай — это функция, которая выполняет минимальное количество шагов для входных данных из n элементов. Наихудший случай — это функция, которая выполняет максимальное количество шагов для входных данных размера n. Средний случай — это функция, которая выполняет среднее количество шагов для входных данных из n элементов.
В вычислениях в реальном времени время выполнения в наихудшем случае часто вызывает особую озабоченность, поскольку важно знать, сколько времени может потребоваться в наихудшем случае, чтобы гарантировать, что алгоритм всегда будет завершаться вовремя.
Средняя производительность и производительность в худшем случае наиболее часто используются в анализе алгоритмов. Менее широко распространена производительность в лучшем случае , но она имеет применение: например, когда известны лучшие случаи отдельных задач, их можно использовать для повышения точности общего анализа в худшем случае. Специалисты по информатике используют методы вероятностного анализа , особенно ожидаемое значение , для определения ожидаемого времени выполнения.
Эти термины используются в других контекстах, например, наихудший и наилучший исход эпидемии, наихудшая температура, воздействию которой подвергается элемент электронной схемы и т. д. Если используются компоненты с указанными допусками , устройства должны быть спроектированы так, чтобы они работали должным образом при наихудшем сочетании допусков и внешних условий.
Термин «лучшая производительность» используется в информатике для описания поведения алгоритма в оптимальных условиях. Например, наилучший случай для простого линейного поиска в списке имеет место, когда искомый элемент является первым элементом списка.
Разработка и выбор алгоритмов редко основываются на наилучшей производительности: большинство академических и коммерческих предприятий больше заинтересованы в улучшении средней сложности и наихудшей производительности . Алгоритмы также могут быть тривиально модифицированы для достижения хорошего наилучшего времени выполнения путем жесткого кодирования решений для конечного набора входных данных, что делает эту меру почти бессмысленной. [1]
Анализ производительности в наихудшем случае и анализ производительности в среднем случае имеют некоторые сходства, но на практике обычно требуют разных инструментов и подходов.
Определить, что означает типичный ввод , сложно, и часто этот средний ввод имеет свойства, которые затрудняют его математическую характеристику (например, рассмотрим алгоритмы, разработанные для работы со строками текста). Аналогично, даже когда возможно разумное описание конкретного «среднего случая» (который, вероятно, будет применим только для некоторых применений алгоритма), они, как правило, приводят к более сложному анализу уравнений. [2]
Анализ наихудшего случая дает безопасный анализ (наихудший случай никогда не недооценивается), но он может быть излишне пессимистичным , поскольку может не быть (реалистичных) входных данных, которые бы позволили выполнить столько шагов.
В некоторых ситуациях может потребоваться использовать пессимистический анализ, чтобы гарантировать безопасность. Однако часто пессимистический анализ может быть слишком пессимистичным, поэтому анализ, который приближается к реальному значению, но может быть оптимистичным (возможно, с некоторой известной низкой вероятностью неудачи), может быть гораздо более практичным подходом. Один из современных подходов в академической теории, позволяющий преодолеть разрыв между анализом худшего и среднего случая, называется сглаженным анализом .
При анализе алгоритмов, которые часто требуют небольшого времени для завершения, но периодически требуют гораздо большего времени, амортизированный анализ может использоваться для определения наихудшего времени выполнения для (возможно бесконечной) серии операций . Эта амортизированная стоимость может быть намного ближе к средней стоимости, при этом по-прежнему обеспечивая гарантированный верхний предел времени выполнения. Так, например, онлайн-алгоритмы часто основаны на амортизированном анализе.
Анализ наихудшего случая связан со сложностью наихудшего случая . [3]
Многие алгоритмы с плохой производительностью в худшем случае имеют хорошую производительность в среднем случае. Для проблем, которые мы хотим решить, это хорошо: мы можем надеяться, что конкретные случаи, которые нас интересуют, являются средними. Для криптографии это очень плохо: мы хотим, чтобы типичные случаи криптографической проблемы были сложными. Здесь методы, такие как случайная саморедуцируемость, могут использоваться для некоторых конкретных проблем, чтобы показать, что наихудший случай не сложнее среднего случая, или, что то же самое, что средний случай не проще наихудшего случая.
С другой стороны, некоторые структуры данных, такие как хэш-таблицы, имеют очень плохое поведение в худшем случае, но хорошо написанная хэш-таблица достаточного размера статистически никогда не даст худшего случая; среднее число выполненных операций следует экспоненциальной кривой спада, и поэтому время выполнения операции статистически ограничено.
