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

В информатике (в частности, в теории сложности вычислений ) сложность наихудшего случая измеряет ресурсы (например, время работы, память ), которые требуются алгоритму с учетом входных данных произвольного размера (обычно обозначаемых как 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.