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