Решение рекуррентных соотношений

Анализ рекурсивных программ. Анализ рекурсивных программ значительно сложнее и, как правило, требует решения дифференциальных уравнений. Мы будем использовать другие методы, которые похожи на методы решения дифференциальных уравнений, и даже позаимствуем их терминологию.
Сначала рассмотрим пример процедуры сортировки (листинг 9.1). Эта функция mergesort (сортировка слиянием) в качестве входных данных использует список элементов длиной n и возвращает этот список отсортированным (выходные данные). Эта функция использует также процедуру merge (слияние), у которой входными данными являются два отсортированных списка L₁ и L₂. Процедура merge(L₁, L₂) просматривает эти списки поэлементно, начиная с наибольших элементов. На каждом шаге наибольший элемент из двух сравниваемых (наибольшие элементы из списков L₁ и L₂) удаляется из своего списка и помещается в выходные данные. В результате получается один отсортированный список, содержащий все элементы из списков L₁ и L₂. Детали выполнения процедуры merge сейчас для нас не имеют значения, сортировка слиянием подробно рассмотрена в главе 11. Сейчас для нас важно только то, что процедура merge на списках длиной n/2 выполняется за время порядка О(n).
Листинг 9.1. Рекурсивная процедура сортировки слиянием
function mergesort { L: LIST; л: integer ): LIST
{ L — список типа LIST длиной л.
Предполагается, что л является степенью числа 2 }
var
LI, L2: LIST
begin
if n = 1 then
return(Z);
else begin
разбиение L на две части LI и ?2, каждая длиной л/2;
return(merge(mergesort(Zl,л/2), (mergesort(Z2,л/2)));
end
end; { mergesort }
Обозначим через Т(п) время выполнения процедуры mergesort в самом худшем случае. Анализируя листинг 9.1, можно записать следующее рекуррентное неравенство, ограничивающее сверху Т(n):
(9.1)
В неравенствах (9.1) константа c₁ соответствует фиксированному количеству шагов, выполняемых алгоритмом над списком L длиной 1. Если n>1, время выполнения процедуры mergesort можно разбить на две части. Первая часть состоит из проверки того, что n≠1, разбиения списка L на две равные части и вызова процедуры merge. Эти три операции требуют или фиксированного времени (проверка n≠1), или пропорционального n — разбиение списка L и выполнение процедуры merge. Поэтому можно выбрать такую константу с₂, что время выполнения этой части процедуры mergesort будет ограничено величиной с₂n. Вторая часть процедуры mergesort состоит из двух рекурсивных вызовов этой процедуры для списков длины n/2, которые требуют времени 2Т(n/2). Отсюда получаем второе неравенство (9.1).
Отметим, что соотношение (9.1) применимо только тогда, когда га четно. Следовательно, формулу для верхней границы Т(n) в замкнутой форме (т.е. в таком виде, когда формула для Т(n) не включает никаких выражений Т(m) для mi) и T(2ⁱ⁺¹), если n лежит между 2ⁱ и 2ⁱ⁺¹. Более того, нетрудно показать, что в (9.1) выражение 2Т(n) можно заменить на Т((n+1)/2)+T((n-1)/2) для нечетных n>1. Таким образом можно найти решение рекуррентного соотношения в замкнутой форме для любых n.