Сложность алгоритмов

Существует несколько  способов измерения сложности алгоритма. Программисты обычно сосредотачивают  внимание на скорости алгоритма, но не менее важны и другие показатели – требования к объёму памяти, свободному месте на диске. Использование быстрого алгоритма не приведёт к ожидаемым  результатам, если для его работы понадобится больше памяти, чем есть у компьютера.

Память  или время

 
Многие алгоритмы предлагают выбор  между объёмом памяти и скоростью. Задачу можно решить быстро, использую  большой объём памяти, или медленнее, занимая меньший объём. 
Типичным примером в данном случае служит алгоритм поиска кратчайшего пути.

Представив кару города в виде сети, можно написать алгоритм для определения кратчайшего  расстояния между двумя любыми точками  этой сети. Чтобы не вычислять эти  расстояния всякий раз, когда они  нам нужны, мы можем вывести кратчайшие расстояния между всеми точками  и сохранить результаты в таблице. Когда нам понадобится узнать кратчайшее расстояние между двумя  заданными точками, мы можем просто взять готовое расстояние из таблицы. Результат будет получен мгновенно, но это потребует огромного объёма памяти. Карта большого города может содержать десятки тысяч точек. Тогда, описанная выше таблица, должна содержать более 10 млрд. ячеек. Т.е. для того, чтобы повысить быстродействие алгоритма, необходимо использовать дополнительные 10 Гб памяти.

Из этой зависимости  проистекает идея объёмно-временной  сложности. При таком подходе  алгоритм оценивается, как с точки  зрении скорости выполнения, так и  с точки зрения потреблённой памяти.

Оценка  порядка

При сравнении различных  алгоритмов важно знать, как их сложность  зависит от объёма входных данных. Допустим, при сортировке одним методом  обработка тысячи чисел занимает 1 с., а обработка миллиона чисел  – 10 с., при использовании другого  алгоритма может потребоваться 2 с. и 5 с. соответственно. В таких условиях нельзя однозначно сказать, какой алгоритм лучше. 
В общем случае сложность алгоритма можно оценить по порядку величины. Алгоритм имеет сложность O(f(n)), если при увеличении размерности входных данных N, время выполнения алгоритма возрастает с той же скоростью, что и функция f(N). 

Средний и наихудший случай

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

function Locate(data: integer): integer;var

i: integer;

fl: boolean;

begin

fl:=false; i:=1;

while (not fl) and (i<=N) do

begin

if A[i]=data then fl:=true else i:=i+1;

end;

if not fl then i:=0;

Locate:=I;

end;

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

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

Оба эти случая маловероятны. Нас больше всего интересует ожидаемый  вариант. Если элемента списка изначально беспорядочно смешаны, то искомый элемент может оказаться в любом месте списка. В среднем потребуется сделать N/2 сравнений, чтобы найти требуемый элемент. Значит сложность этого алгоритма в среднем составляет O(N/2)=O(N).

В данном случае средняя  и ожидаемая сложность совпадают, но для многих алгоритмов наихудший  случай сильно отличается от ожидаемого. Например, алгоритм быстрой сортировки в наихудшем случае имеет сложность порядка O(N^2), в то время как ожидаемое поведение описывается оценкой O(N*log(N)), что много быстрее.

Общие функции оценки сложности

Сейчас мы перечислим некоторые функции, которые чаще всего используются для вычисления сложности. Функции перечислены  в порядке возрастания сложности. Чем выше в этом списке находится  функция, тем быстрее будет выполняться  алгоритм с такой оценкой.

• C – константа
• log(log(N))
• log(N)
• N^C, 0<C<1
• N
• N*log(N)
• N^C, C>1
• C^N, C>1
• N!

Если мы хотим оценить  сложность алгоритма, уравнение  сложности которого содержит несколько  этих функций, то уравнение можно  сократить до функции, расположенной  ниже в таблице. Например, O(log(N)+N!)=O(N!).

Если алгоритм вызывается редко и для небольших объёмов  данных, то приемлемой можно считать  сложность O(N^2), если же алгоритм работает в реальном времени, то не всегда достаточно производительности O(N).

Обычно алгоритмы  со сложностью N*log(N) работают с хорошей скоростью. Алгоритмы со сложностью N^C можно использовать только при небольших значениях C. Вычислительная сложность алгоритмов, порядок которых определяется функциями C^N и N! очень велика, поэтому такие алгоритмы могут использоваться только для обработки небольшого объёма данных.

Сложность рекурсивных алгоритмов

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

function Factorial(n: Word): integer; 
begin 
if n > 1 then 
Factorial:=n*Factorial(n-1) 
else 
Factorial:=1; 
end;

Эта процедура выполняется N раз, таким образом, вычислительная сложность этого алгоритма равна O(N).

Многократная рекурсия

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

procedure DoubleRecursive(N: integer); 
begin 
if N>0 then 
begin 
DoubleRecursive(N-1); 
DoubleRecursive(N-1); 
end; 
end;

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

Объемная  сложность рекурсивных  алгоритмов

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