Наихудшая сложность

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

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