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

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

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

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

Определение [ править ]

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

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

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

входов $s$ с длиной или размером $\leq n$ .

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

Способы речи [ править ]

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

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

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

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

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

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

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

Примеры [ править ]

Рассмотрите возможность вставкой сортировки $n$ числа на машине с произвольным доступом . Наилучший случай для алгоритма — это когда числа уже отсортированы, что требует $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.