Сложность в худшем случае

Верхняя граница ресурсов, необходимых алгоритму

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

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

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

Определение

При наличии модели вычислений и алгоритма , который останавливается на каждом входе , отображение называется временной сложностью , если для каждой входной строки останавливается ровно через шагов. ${\displaystyle {\mathsf {A}}}$ ${\displaystyle s}$ ${\displaystyle t_{\mathsf {A}}\colon \{0,1\}^{\star }\to \mathbb {N} }$ ${\displaystyle {\mathsf {A}}}$ ${\displaystyle s}$ ${\displaystyle {\mathsf {A}}}$ ${\displaystyle t_{\mathsf {A}}(s)}$

Поскольку мы обычно интересуемся зависимостью временной сложности от различных длин входных данных, то, злоупотребляя терминологией, временную сложность иногда относят к отображению , определяемому максимальной сложностью ${\displaystyle t_{\mathsf {A}}\colon \mathbb {N} \to \mathbb {N} }$

${\displaystyle t_{\mathsf {A}}(n):=\max _{s\in \{0,1\}^{n}}t_{\mathsf {A}}(s)}$

входных данных длиной или размером . ${\displaystyle s}$ ${\displaystyle \leq n}$

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

Способы речи

Очень часто сложность алгоритма задается в асимптотической нотации Big-O , которая представляет ее темп роста в виде с определенной вещественнозначной функцией сравнения и имеет смысл: ${\displaystyle t_{\mathsf {A}}}$ ${\displaystyle {\mathsf {A}}}$ ${\displaystyle t_{\mathsf {A}}=O(g(n))}$ ${\displaystyle g(n)}$

• Существует положительное действительное число и натуральное число, такие что ${\displaystyle M}$ ${\displaystyle n_{0}}$

${\displaystyle |t_{\mathsf {A}}(n)|\leq Mg(n)\quad {\text{ for all }}n\geq n_{0}.}$

Довольно часто встречается следующая формулировка:

• «Алгоритм имеет наихудшую сложность ». ${\displaystyle {\mathsf {A}}}$ ${\displaystyle O(g(n))}$

или даже только:

• «Алгоритм имеет сложность ». ${\displaystyle {\mathsf {A}}}$ ${\displaystyle O(g(n))}$

Примеры

Рассмотрим выполнение сортировки вставкой чисел на машине с произвольным доступом . Наилучший случай для алгоритма — когда числа уже отсортированы, что требует шагов для выполнения задачи. Однако в худшем случае входные данные для алгоритма — когда числа отсортированы в обратном порядке, и требуется несколько шагов для их сортировки; поэтому наихудшая временная сложность сортировки вставкой составляет . ${\displaystyle n}$ ${\displaystyle O(n)}$ ${\displaystyle O(n^{2})}$ ${\displaystyle 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.