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

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

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

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

Определение

Дана модель вычислений и алгоритм A {displaystyle {mathsf {A}}} , который останавливается на каждом входе s {displaystyle s} , соответствие t A : { 0 , 1 } ⋆ → N {displaystyle t_{mathsf {A}}colon {0,1}^{star } o mathbb {N} } называется временной сложностью алгоритма A {displaystyle {mathsf {A}}} если, для каждой входной строки s {displaystyle s} , A {displaystyle {mathsf {A}}} останавливается точно после t A ( s ) {displaystyle t_{mathsf {A}}(s)} шагов.

Так как нас обычно интересует зависимость временной сложности алгоритма на входных данных различной длины, злоупотребляя терминологий, временной сложностью алгоритма иногда называют соответствие t A : N → N {displaystyle t_{mathsf {A}}colon mathbb {N} o mathbb {N} } , определяемое максимальной сложностью

t A ( n ) := max s ∈ { 0 , 1 } n t A ( s ) {displaystyle t_{mathsf {A}}(n):=max _{sin {0,1}^{n}}t_{mathsf {A}}(s)}

входных данных s {displaystyle s} длиной или размером ≤ n {displaystyle leq n} .

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

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

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

• Существует позитивное вещественное число M {displaystyle M} и натуральное число n 0 {displaystyle n_{0}} такие, что

| t A ( n ) | ≤ M g ( n )  для всех  n ≥ n 0 . {displaystyle |t_{mathsf {A}}(n)|leq Mg(n)quad { ext{ для всех }}ngeq n_{0}.}

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

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

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

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

Примеры

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