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