Понятие алгоритма и меры его сложности. Временная и емкостная сложность алгоритмов

5. Анализ сложности рекурсивных алгоритмов

Рассмотрим сначала случай прямой рекурсии с единственным (вне какого-либо цикла) рекурсивным вызовом в теле процедуры. Примером такого алгоритма является алгоритм Евклида вычисления наибольшего общего делителя. Текст рекурсивной процедуры с вектором исходных данных X содержит вызов этой же процедуры с измененным по некоторому правилу вектором исходных данных Y = f(X). Кроме этого, в тексте содержится некоторое нерекурсивное вычисление h(X) и операции сравнения c(Х,S) значения X со значением S, при котором рекурсивный процесс должен заканчиваться. Обозначим "точное" (а не верхнюю границу или среднее) значение сложности при входных данных X через Тa(X). Тогда

Тa(X) = Тa(Y)+Th(X)+Tc(X,S), или Тa(X) = Тa(АХ))+Tf(X)+Th(X)+ Tc(X,S).

Второе соотношение представляет собой рекуррентное уравнение для определения значений неизвестной функции Тa(X) через известные значения f(A), Tf(X), Th(X), Tc(X,S). Кроме этого, имеется начальное условие Ta(S)=Ts(S) с известной функцией сложности вычисления (нерекурсивного) значения S. Таким образом, имеется система:

Тa(Х) =Ta(f(X))+ Tf(X)+Th(X)+ Тc(X, S)a(S)=Tc(S,S)+Ts(S)

Это частный случай рекуррентного уравнения. Такие уравнения имеют развитую теорию. В некоторых случаях возможно аналитическое решение. Покажем его применение на примере рекурсивного вычисления факториала:

function FACTORIAL (х: integer): integer;x = 1 then FACTORIAL:= 1FACTORIAL:= x * FACTORIAL (x-1);;

Здесь X=x, S=1, f(X)=X-1, Tf(X)=1, Th(X) = 2, Tc(X,S)=l, Ts(S) = 1. Таким образом, система уравнений превращается в Тa(x) = Тa(х-1)+4, Тa(1) = 2. Ее решение - Тa(x) = 4х-2.

Верхняя оценка Тa(V) может быть получена подобным образом, но с использованием рекуррентных неравенств:

Тa(V) <= Тa(f(V))+Tf(V)+Th(V)+Tc(V,V0),a(V0) <= Tc(V0, Vo)+Ts(V0).

Оценка среднего значения сложности требует учета вероятностных законов и может быть значительно более трудной. Вообще говоря, нельзя использовать написанные выше рекуррентные уравнения в вероятностном случае: среднее значение функции случайной величины не равно значению функции от среднего значения случайной величины, среднее (f(X)) <> f(среднее (X)), кроме случая линейной функции f.
Теперь рассмотрим более общий случай прямой рекурсии (4, стр. 402-404) с несколькими рекурсивными вызовами в теле процедуры. Эти вызовы могут иметь разные аргументы Y1, Y2, . . . ,Yk, где Y1 =fl(X), Y2 =f2(X), ..., Yk=fk(X). Рекуррентное уравнение для функции сложности имеет вид

Тa(X) = Тa(f1(X)) + Тa(f2(X)) + ... + Тa(fk(X)) + Tf1(X) + Тf2(X) + ...+Тfk(X) + Тh (X) + Tc (X, S)

Тaa(S) = Tc (S, S) + Ts (S).