1. Общий случай определения сложности

Оценку сложности алгоритмов выполняют с использованием аппарата математического асимптотического анализа и выведения асимптотической оценки сложности.

Выражения (1.1) – (1.5) представляют собой асимптотические оценки сложности соответствующих алгоритмов. В теории алгоритмов они являются семейством функций, дающих множество значений, в том числе верхнее и нижнее. Основным свойством Θ(n) является то, что при увеличении размерности входных данных n время выполнения алгоритма возрастает с той же скоростью, что и функция f(n).

Асимптотическая оценка сложности, как видно из примеров, обозначается греческой буквой Θ (тета).

f(n) = Θ(g(n)), если существуют c₁, c₂>0 и n₀ такие, что c₁*g(n)<=f(n)<=c₂*g(n) , при n>n₀.

Функция g(n) является асимптотически точной оценкой сложности алгоритма - функции f(n). Приведенное неравенство называется асимптотическим, а само обозначение Θ символизирует множество функций, которые растут «так же быстро», как и функция g(n) – т.е. с точностью до некоторой константы c₁ или c₂.

Как следует из приведенного неравенства, Θ представляет собой одновременно и верхнюю, и нижнюю оценки сложности. Не всегда имеется возможность получить выражение в общем виде, поэтому верхнюю и нижнюю оценки могут определять отдельно.

Верхняя оценка сложности обозначается греческой буквой Ο (омикрон), и является множеством функций, которые растут не быстрее, чем g(n).

f(n)= Ο(g(n)), если существует c>0 и n₀ такие, что 0<=f(n)<=cg(n), при n>n₀.

Нижняя оценка сложности обозначается греческой буквой Ω (омега), и является множеством функций, которые растут не медленнее, чем g(n).

f(n)= Ω(g(n)), если существует c>0 и n0 такие, что 0<=cg(n)<=f(n), при n>n₀.

Вообще, асимптотическая оценка существует только в том случае, если совпадают нижняя и верхняя оценки сложности алгоритма. В практике анализа алгоритмов чаще всего используют верхнюю оценку. Это вполне логично, поскольку наиболее важна оценка времени, за которое алгоритм гарантировано закончит работу, а не время, в пределах которого он точно не завершится.

Таким образом, считается, что верхняя оценка сложности пропорциональна максимальному элементу в формуле Θ(n) (см. (1.1) – (1.5)). Она легче вычисляется и дает предельное значение. Именно она получила наибольшее распространение.

Обычно определение сложности алгоритма сводится к анализу

1. Циклов;

2. Вызовов методов и

3. Вызовов рекурсий.

Так, в примере 1 (нахождение суммы элементов квадратной матрицы) она определяется величиной O(n²), а в примере 2 (нахождение максимума в одномерном массиве) для всех случаев – O(n). Вообще для циклов вида:

for (i=1; i<= n;i++)

for (j=1; j<= n;j++)

for (k=1; k<= n;k++)

{Тело цикла}

сложность равна O(n³), т.е. пропорциональна числу повторений самого внутреннего цикла.

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

В качестве примера рассмотрим два метода: slow со сложностью O(n³) и fast со сложностью O(n²).

public static slow{

int i,j,k;

for (i=1; i<= n;i++)

for (j=1; j<= n;j++)

for (k=1; k<= n;k++)

{Операции обработки информации}

return Результат}

public static fast {

int i,j;

for (i=1; i<= n;i++)

for (j=1; j<= n;j++)

Slow;

return Результат}

public static both {

Fast;

return Результат}

Если во внутренних циклах fast происходит вызов метода slow, то сложности методов перемножаются, т.е. сложность алгоритма составляет O(n²)*O(n³)=O(n⁵). Если же основная программа вызывает процедуры по очереди, то их сложности складываются: O(n²) + O(n³)=O(n³). Следующий фрагмент имеет именно такую сложность.

public static slow{

int i,j,k;

for (i=1; i<= n;i++)

for (j=1; j<= n;j++)

for (k=1; k<= n;k++)

{Операции обработки информации}

return Результат}

public static Fast {

int i,j;

for (i=1; i<= n;i++)

for (j=1; j<= n;j++)

{Операции обработки информации}

return Результат}

public static both {

slow;

fast;

return Результат}

Рекурсивными называются функции (процедуры, методы), которые вызывают сами себя. Сложность этих алгоритмов зависит не только от сложности внутренних циклов, но и от количества итераций самой рекурсии. Такая функция может выглядеть достаточно простой, но она может серьёзно усложнить программу за счет многократных вызовов.

Рассмотрим рекурсивную реализацию вычисления факториала в среде java.

int factorial(int n){

if (n > 1)

rezult:=n*factorial(n-1)

else

rezult:=1;

return rezult;

};

Она выполняется n раз. Таким образом, вычислительная сложность этого алгоритма равна O(n).

Рекурсивный алгоритм, который вызывает себя несколько раз, называется многократной рекурсией. Такие процедуры гораздо сложнее анализировать. При этом сложность алгоритма возрастает. Рассмотрим такую функцию.

int doublerecursive(int n){

if (n>0)

doublerecursive(n-1);

doublerecursive(n-1);

}

Поскольку процедура вызывается дважды, можно было бы предположить, что её рабочий цикл будет равен O(2n)=O(n). Но на самом деле ситуация гораздо сложнее. Если внимательно исследовать этот алгоритм, то станет очевидно, что его сложность равна O(2ⁿ⁺¹-1)=O(2ⁿ). Таким образом, анализ сложности рекурсивных алгоритмов весьма нетривиальная задача.