На этом шаге мы рассмотрим анализ сложности рекурсивных алгоритмов.
Рассмотрим сначала случай прямой рекурсии с единственным (вне какого-либо цикла) рекурсивным вызовом в теле процедуры. Примером такого алгоритма является алгоритм Евклида вычисления наибольшего общего делителя.
Напомним, что текст рекурсивной процедуры с вектором исходных данных X содержит вызов этой же процедуры с измененным по некоторому правилу вектором исходных данных Y = f(X). Кроме этого, в тексте содержится некоторое нерекурсивное вычисление h(X) и операции сравнения c(Х,S) значения X со значением S, при котором рекурсивный процесс должен заканчиваться. Обозначим "точное" (а не верхнюю границу или среднее) значение сложности при входных данных X через Тα(X). Тогда
Тα(X) = Тα(Y) + Th(X) + Tc(X,S),
или
Тα(X) = Тα(АХ)) + Tf(X) + Th(X) + Tc(X,S).
Второе соотношение представляет собой рекуррентное уравнение для определения значений неизвестной функции Тα(X) через известные значения f(A), Tf(X), Th(X), Tc(X,S). Кроме этого, имеется начальное условие Tα(S)=Ts(S) с известной функцией сложности вычисления (нерекурсивного) значения S. Таким образом, имеется система:
Тα(Х) =Tα(f(X))+ Tf(X)+Th(X)+ Тc(X, S) Tα(S)=Tc(S,S)+Ts(S)
Это частный случай рекуррентного уравнения. Такие уравнения имеют развитую теорию. В некоторых случаях возможно аналитическое решение. Покажем его применение на примере рекурсивного вычисления факториала:
function FACTORIAL (х: integer): integer; begin if x = 1 then FACTORIAL:= 1 else FACTORIAL:= x * FACTORIAL (x-1); end;
Здесь X = x, S = 1, f(X)=X-1, Tf(X)=1, Th(X) = 2, Tc(X,S)=l, Ts(S) = 1. Таким образом, система уравнений превращается в
Тα(x) = Тα(х-1)+4, Тα(1) = 2.
Ее решение - Тα(x) = 4х-2.
Верхняя оценка Тα(V) может быть получена подобным образом, но с использованием рекуррентных неравенств:
Тα(V) <= Тα(f(V))+Tf(V)+Th(V)+Tc(V,V0), Tα(V0) <= Tc(V0, Vo)+Ts(V0).
Оценка среднего значения сложности требует учета вероятностных законов и может быть значительно более трудной. Вообще говоря, нельзя использовать написанные выше рекуррентные уравнения в вероятностном случае: среднее значение функции случайной величины не равно значению функции от среднего значения случайной величины,
среднее (f(X)) <> f(среднее (X)),
кроме случая линейной функции f.
Теперь рассмотрим более общий случай прямой рекурсии с несколькими рекурсивными вызовами в теле процедуры. Эти вызовы могут иметь разные аргументы Y1, Y2, . . . ,Yk, где Y1 =fl(X), Y2 =f2(X), ..., Yk=fk(X). Рекуррентное уравнение для функции сложности имеет вид
Тα(X) = Тα(f1(X)) + Тα(f2(X)) + ... + Тα(fk(X)) + Tf1(X) + Тf2(X) + ...+
Тfk(X) + Тh (X) + Tc (X, S)
Тα(S) = Tc (S, S) + Ts (S).
В реальных рекурсивных алгоритмах встречаются различные функции fi(X), однако, подчиняющиеся обычно определенным закономерностям. Эти наиболее часто встречающиеся случаи мы сейчас рассмотрим.
1. Одинаковые функции fl(X) = ...= fk(X) = f(X). Рекуррентное уравнение для функции сложности имеет вид:
Тα(X) = k Тα (f(Х))+kTf(X)+Th(X) + ТС(Х, S),
Tα(S)=Tc(S,S)+Ts(S).
Решение этого уравнения зависит от соотношения k и f(X). Ясно, что если k > 1, то значения Tα (X) быстро возрастают с ростом X (если значения могут быть упорядочены) или Tα (V) быстро возрастают с ростом V, если функция f недостаточно быстро уменьшает X. Первый пример как раз такого рода: k = 2, f(X)=Х-1.
Проведем анализ решения известной головоломки "Ханойская башня" (рисунок 1) - игры, основанной на древнем ритуале брахманской башни, с помощью которого, по преданию, брахманские жрецы предсказывали конец света.
Рис.1. Ханойская башня
Задача состоит в следующем.
Имеется три алмазных иглы: a, b, c. В момент творения на иглу а нанизываются 64 золотых диска уменьшающихся размеров (будем рассматривать задачу для n дисков). Все диски имеют разный диаметр, внизу находится самый большой диск, а наверху - самый маленький. Никакой диск большего диаметра не может находиться выше диска меньшего диаметра. На иглах b и с дисков нет. Перед брахманскими жрецами, только что посвященными в сан, ставится задача переложить диски на иглу b. При этом иглой с можно пользоваться как временной емкостью. Конец света наступит, когда все 64 диска окажутся на игле b в том же порядке, в котором они располагались на игле a.
С алгоритмической точки зрения элементарным шагом является перенос одного диска. В задаче имеется важное ограничение: ни на одной из игл никогда не должно возникать ситуации, при которой диск большего диаметра лежит на диске меньшего диаметра.
Рекурсивное решение этой задачи выглядит естественно и просто. Пусть процедура CARRY (n, а, b, c) переносит башню высоты n с иглы а на иглу b, используя иглу c как вспомогательную. Тогда исходная задача может быть разбита на три части:
CARRY (n-1, а, с, b) {Перенести верхние n-1 дисков на с.} CARRY (1, а, b, - ); {Перенести один (нижний) диск на b.} CARRY (n-1, с, b, а);{Перенести башню с c на большой диск, уже находящийся на b.}
Вторая часть тривиальная, одношаговая. Выделим ее в отдельную нерекурсивную процедуру ONEDISK (a,b). Теперь можно написать рекурсивную процедуру:
procedure CARRY (n, а, b, c: integer); begin if n > 1 then begin CARRY (n-1, а, с, b); ONEDISK (a,b); CARRY (n-1, c, b, a) end; end;
Сложность процедуры ONEDISK - константа (обозначим ее K). Входной набор Z = (n, а, b, с). Достаточно очевидно, что номера игл а, b, с никак не влияют на сложность. Поэтому можно принять V = n. Рекурсивное уравнение примет вид:
Тα (n) = 2Тα (n-1) +2 + h + 1, Тα (1) = 1 + 0, или Тα (n) = 2Тa (n-1) + h + 3, Тα (1) = 1.
Решение этого уравнения может быть получено в виде:
Тα (n) = v 2n + w,
где v, w - параметры, подлежащие определению.
Уравнения для определения v и w получаются из предыдущих рекуррентных соотношений:
v2n + w = 2v2(n-1) + 2w + h + 3, v2 + w = 1
Итого,
Tα (n) = (2 + h/2) 2n - (h + 3).
Найденная оценка сложности относится к классу так называемых экспоненциальных функций временной сложности.
Второй тип рекуррентных уравнений, часто встречающихся в анализе алгоритмов, может быть задан следующими формулами:
Tα (V) = k Tα (V/m) +lV, Тα (1) = l,
при этом предполагается, что сложность данных V - натуральное число.
При отсутствии явного выражения решения в виде формулы, включающей элементарные функции, обычно удовлетворяются асимптотическим решением, т. е. приближенной формулой, точность которой возрастает с ростом V.
Асимптотическое решение уравнений этого типа будет следующим:
Тα (V) = О (V), если k < m, Тα (V) = О (V logV), если k = m, Тα (V) = О (V logmk), если k > m.
2. Функции, образующие прогрессию Х-1, Х-2, ..., Х-k.
Пример такой процедуры для k-2 уже был приведен - рекурсивная процедура для нахождения n-го числа Фибоначчи. Проведем более детальный ее анализ.
function Fr (n: integer): integer; begin if n = 1 or n = 2 then Fr := 1 else Fr := Fr(n-1) + Fr(n-2); end;
Здесь сразу можно взять Х= n, Tf1(n) = Tf2(n) = 1, Th (n) = 2, Тс(n) = 2, Ts (n) = 1. Уравнения для функции сложности: Тα (n) = Тα (n-1) + Тα (n-2) + 6, Тα (2) = 3, Тα (1) = 3.
На следующем шаге мы рассмотрим случай косвенной рекурсии.
