В информатике сложность наихудшего случая (обычно обозначаемая в асимптотической нотации) измеряет ресурсы (например, время работы, память), которые требуются алгоритму при вводе произвольного размера (обычно обозначаемом как n или N ). Это дает верхнюю границу ресурсов, требуемых алгоритмом.
В случае времени выполнения наихудшая временная сложность указывает самое продолжительное время выполнения, выполняемое алгоритмом при любом вводе размера n , и, таким образом, гарантирует, что алгоритм завершится в указанный период времени. Порядок роста (например, линейный, логарифмический) сложности наихудшего случая обычно используется для сравнения эффективности двух алгоритмов.
Сложность алгоритма в наихудшем случае следует противопоставлять его сложности в среднем случае , которая является средней мерой количества ресурсов, которые алгоритм использует для случайного ввода.
Определение
Учитывая модель вычислений и алгоритм A , который останавливается на каждой входной х , отображение т А : {0, 1} * → N называется временная сложность из А , если для каждого х , A останавливается после точно т ( х ) шаги.
Поскольку нас обычно интересует зависимость временной сложности от различной длины входных данных, злоупотребляя терминологией, временную сложность иногда называют отображением T A : N → N , определяемым T A ( n ): = max x ∈ {0 , 1} n {t A ( x )}.
Аналогичные определения могут быть даны для пространственной сложности, сложности случайности и т. Д.
Примеры
Рассмотрим выполнение вставки сортировать по п чисел на случайной машине доступа . В лучшем случае для алгоритма числа уже отсортированы, что требует O ( n ) шагов для выполнения задачи. Однако вход в наихудшем случае для алгоритма - это когда числа отсортированы в обратном порядке, и для их сортировки требуется O ( n 2 ) шагов; поэтому наихудшая временная сложность сортировки вставкой составляет O ( n 2 ).
Смотрите также
Рекомендации
- Томас Х. Кормен , Чарльз Э. Лейзерсон , Рональд Л. Ривест и Клиффорд Штайн . Введение в алгоритмы , второе издание. MIT Press и McGraw-Hill, 2001. ISBN 0-262-03293-7 . Глава 2.2: Анализирующие алгоритмы, стр.25-27.
- Одед Гольдрайх. Вычислительная сложность: концептуальная перспектива. Издательство Кембриджского университета, 2008. ISBN 0-521-88473-X , стр.32.