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

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

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

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

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

• „Алгоритм ${\mathsf {A}}$ имеет сложность $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 0-262-03293-7. Chapter 2.2: Analyzing algorithms, pp.25-27.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press, 2008. ISBN 0-521-88473-X, p.32.