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

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

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

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

Очень часто, сложность ${\displaystyle t_{\mathsf {A}}}$ алгоритма ${\displaystyle {\mathsf {A}}}$ дана в асимптотическом Big-O обозначении, которое обозначает его рост в форме ${\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{ для всех }}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})}$.

См. также

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

Ссылки

• 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.