Худший случай сложности

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

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

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

Определение

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

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

$t_{𝖠}(n):=\underset{s\in \{0,1{\}}^n}{\max }{t}_{𝖠}(s)$

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

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

Способы формулировки

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

• Существует позитивное вещественное число $M$ и натуральное число $n_0$ такие, что

$|t_{𝖠}(n)|\le Mg(n)\text{ для всех }n\ge n_0.$

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

• „Алгоритм $𝖠$ имеет худший случай сложности $O(g(n))$.“

или еще короче:

• „Алгоритм $𝖠$ имеет сложность $O(g(n))$.“

Примеры

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

См. также

• Теория алгоритмов

Ссылки

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. Шаблон:ISBN. Chapter 2.2: Analyzing algorithms, pp.25-27.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. Шаблон:ISBN, p.32.