> (Х) = T a (f (X)) + Tf (X) + Th (X) + тс (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) + i К (X) + Tc (X, S)
Т aa (S) = Tc (S, S) + Ts (S).
6. Оптимізація алгоритмів
Поки комп'ютерні науки витратило не накопичили достатньо ві...
