Сложность наихудшего случая - Worst-case complexity

В информатике сложность наихудшего случая (обычно обозначаемая в асимптотической нотации) измеряет ресурсы (например, время работы, память), которые требуются алгоритму при вводе произвольного размера (обычно обозначаемом как 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.
  • Одед Гольдрайх. Вычислительная сложность: концептуальная перспектива. Cambridge University Press, 2008. ISBN  0-521-88473-X , стр.32.