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

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

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

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

Определение

Учитывая модель вычисления и алгоритм А который останавливается на каждом входе Иксотображение тА:{0, 1}*→N называется временная сложность из А если для каждого Икс, А останавливается точно после тА(Икс) шаги.

Поскольку нас обычно интересует зависимость временная сложность на разной длине ввода, злоупотребляя терминологией, временную сложность иногда относят к отображению TА:N→N, определяемый TА(п): = макс.Икс∈{0, 1}п{тА(Икс)}.

Аналогичные определения могут быть даны для пространственной сложности, сложности случайности и т. Д.

Примеры

Рассмотрите возможность выполнения вставка сортировки на п числа на машина с произвольным доступом. Наилучший случай для алгоритма - когда числа уже отсортированы, что занимает O (п) шаги для выполнения задачи. Однако вход в худшем случае для алгоритма - это когда числа отсортированы в обратном порядке, и для этого требуется O (п2) шаги по их сортировке; следовательно, сложность сортировки вставкой в ​​наихудшем случае равна O (п2).

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

Рекомендации

  • Томас Х. Кормен, Чарльз Э. Лейзерсон, Рональд Л. Ривест, и Клиффорд Штайн. Введение в алгоритмы, Второе издание. MIT Press и McGraw-Hill, 2001. ISBN  0-262-03293-7. Глава 2.2: Анализирующие алгоритмы, стр.25-27.
  • Одед Гольдрайх. Вычислительная сложность: концептуальная перспектива. Издательство Кембриджского университета, 2008. ISBN  0-521-88473-X, стр.32.