Лучший, худший и средний случай

Эта статья нуждается в дополнительных ссылках для проверки . Пожалуйста, помогите улучшить эту статью , добавив ссылки на надежные источники . Неисходный материал может быть оспорен и удален. Найдите источники:  «Лучший, худший и средний случай»  —  новости  · газеты  · книги  · ученый  · JSTOR ( март 2009 г. ) ( узнайте, как и когда удалить это шаблонное сообщение )

В информатике лучший , худший и средний случаи данного алгоритма выражают , каково использование ресурсов по крайней мере , не более и в среднем соответственно. Обычно рассматриваемым ресурсом является время выполнения, т . е. временная сложность , но также может быть память или другой ресурс. В лучшем случае это функция, которая выполняет минимальное количество шагов на входных данных из n элементов. В худшем случае это функция, которая выполняет максимальное количество шагов на входных данных размера n. Средний случай — это функция, которая выполняет среднее количество шагов для входных данных из n элементов.

В вычислениях в реальном времени время выполнения в наихудшем случае часто вызывает особую озабоченность, поскольку важно знать, сколько времени может потребоваться в наихудшем случае , чтобы гарантировать, что алгоритм всегда завершится вовремя.

Средняя производительность и производительность в наихудшем случае наиболее часто используются при анализе алгоритмов. Менее распространена производительность в наилучшем случае , но она имеет применение: например, когда известны лучшие случаи отдельных задач, их можно использовать для повышения точности общего анализа наихудшего случая. Ученые- компьютерщики используют методы вероятностного анализа , особенно математическое ожидание , для определения ожидаемого времени работы.

Термины используются в других контекстах; например, наихудший и наилучший исход эпидемии, наихудшая температура, которой подвергается элемент электронной схемы, и т. д. Если используются компоненты с заданным допуском , устройства должны быть рассчитаны на правильную работу в наихудшем сочетании. допусков и внешних условий.

Наилучшая производительность для алгоритма

Термин производительность в лучшем случае используется в информатике для описания поведения алгоритма в оптимальных условиях. Например, наилучший случай простого линейного поиска в списке возникает, когда искомый элемент является первым элементом списка.

Разработка и выбор алгоритмов редко основываются на производительности в наилучшем случае: большинство академических и коммерческих предприятий больше заинтересованы в улучшении сложности в среднем и производительности в наихудшем случае . Алгоритмы также могут быть тривиально модифицированы, чтобы иметь хорошее время работы в лучшем случае, путем жесткого кодирования решений для конечного набора входных данных, что делает измерение почти бессмысленным. ^[1]

Производительность в худшем случае и в среднем

В этом разделе не цитируются никакие источники . Пожалуйста, помогите улучшить этот раздел , добавив ссылки на надежные источники . Неисходный материал может быть оспорен и удален . ( сентябрь 2017 г. ) ( узнайте, как и когда удалять это шаблонное сообщение )

Анализ производительности в наихудшем случае и анализ производительности в среднем имеют некоторое сходство, но на практике обычно требуют разных инструментов и подходов.

Определить, что означает типичный ввод , сложно, и часто этот средний ввод имеет свойства, которые затрудняют его математическую характеристику (рассмотрим, например, алгоритмы, разработанные для работы со строками текста). Точно так же, даже когда возможно разумное описание конкретного «среднего случая» (которое, вероятно, будет применимо только для некоторых применений алгоритма), они, как правило, приводят к более сложному анализу уравнений. ^[2]

Анализ наихудшего случая дает безопасный анализ (наихудший случай никогда не недооценивается), но он может быть чрезмерно пессимистичным , поскольку может не быть (реалистичных) входных данных, которые потребовали бы такого количества шагов.

В некоторых ситуациях может оказаться необходимым использовать пессимистический анализ, чтобы гарантировать безопасность. Однако часто пессимистический анализ может быть слишком пессимистичным, поэтому анализ, который приближается к реальному значению, но может быть оптимистичным (возможно, с некоторой известной низкой вероятностью неудачи), может оказаться гораздо более практичным подходом. Один из современных подходов в академической теории для преодоления разрыва между анализом наихудшего и среднего случаев называется сглаженным анализом .

При анализе алгоритмов, которые часто требуют небольшого времени для завершения, но периодически требуют гораздо большего времени, амортизированный анализ может использоваться для определения наихудшего времени выполнения (возможно, бесконечного) ряда операций . Эта амортизированная стоимость в худшем случае может быть намного ближе к средней стоимости, но при этом обеспечивает гарантированный верхний предел времени работы.

Анализ наихудшего случая связан со сложностью наихудшего случая . ^[3]

Практические последствия

Многие алгоритмы с плохой производительностью в худшем случае имеют хорошую производительность в среднем. Для проблем, которые мы хотим решить, это хорошо: мы можем надеяться, что конкретные экземпляры, которые нас интересуют, являются средними. Для криптографии это очень плохо: мы хотим, чтобы типичные экземпляры криптографической проблемы были сложными. Здесь такие методы, как случайная саморедукция , могут использоваться для некоторых конкретных задач, чтобы показать, что наихудший случай не сложнее, чем средний случай, или, что то же самое, что средний случай не легче, чем наихудший случай.

С другой стороны, некоторые структуры данных, такие как хеш-таблицы , имеют очень плохое поведение в наихудшем случае, но хорошо написанная хэш-таблица достаточного размера статистически никогда не даст наихудшего случая; среднее количество выполненных операций соответствует экспоненциальной кривой затухания, поэтому время выполнения операции статистически ограничено.

Примеры

Алгоритмы сортировки

• Сортировка вставками применяется к списку из n элементов, которые считаются разными и изначально расположены в случайном порядке. В среднем половина элементов в списке A ₁ ... A _j меньше элемента A _{j +1} , а половина больше. Следовательно, алгоритм сравнивает ( j  + 1) ^-й элемент, который нужно вставить, в среднем с половиной уже отсортированного подсписка, так что t _j = j /2. Вычисление результирующего времени выполнения в среднем случае дает квадратичную функцию размера входных данных, как и время выполнения в наихудшем случае.
• Быстрая сортировка применяется к списку из n элементов, опять же предполагается, что все они разные и изначально расположены в случайном порядке. Этот популярный алгоритм сортировки в среднем имеет производительность O( n  log( n )), что делает его очень быстрым на практике. Но при наихудшем входе его производительность снижается до O( n ² ). Кроме того, при реализации с политикой «самый короткий первый» сложность пространства в наихудшем случае вместо этого ограничивается O (log ( n )).
• Heapsort имеет время O (n), когда все элементы одинаковы. Heapify занимает время O(n), а затем удаление элементов из кучи занимает время O(1) для каждого из n элементов. Время выполнения увеличивается до O(nlog(n)), если все элементы должны быть разными.
• Bogosort имеет время O (n), когда элементы сортируются на первой итерации. На каждой итерации все элементы проверяются на правильность. Нет! возможные перестановки; со сбалансированным генератором случайных чисел почти каждая перестановка массива дает n! итерации. Компьютеры имеют ограниченную память, поэтому генерируемые числа циклически повторяются; может быть невозможно достичь каждой перестановки. В худшем случае это приводит к времени O(∞), бесконечному циклу.

Структуры данных

• Линейный поиск в списке из n элементов. В самом худшем случае поиск должен посетить каждый элемент один раз. Это происходит, когда искомое значение либо является последним элементом в списке, либо отсутствует в списке. Однако в среднем, если предположить, что искомое значение находится в списке, и каждый элемент списка с равной вероятностью является искомым значением, поиск посещает только n /2 элементов.

Смотрите также

• Алгоритм сортировки — область, в которой проводится большой объем анализа производительности различных алгоритмов.
• Структура данных поиска — любая структура данных, позволяющая эффективно находить определенные элементы.
• Анализ схемы в наихудшем случае
• Сглаженный анализ
• Интервальный конечный элемент
• Обозначение большого O

использованная литература