Analiza algorytmów rekurencyjnych
Równania rekurencyjne
Równania rekurencyjne
Metody rozwiązywania równań rekurencyjnych:
Przewidywanie rozwiązania (dowód indukcyjny)
Iterowanie rekurencji, rozwinięcie rekurencyjne  w sumę
Metoda rekurencji uniwersalnej
Podstawowe typy równań rekurencyjnych:
Równania typu  dziel i zwyciężaj
Równania typu  jeden krok wstecz
ASD LJ S
1
Metody rozwiązywania
Przewidywanie rozwiązania.
Wartość funkcji T(n) obliczana jest na podstawie wartości bezpośrednio
poprzedzającej T(n-1):
c dla n = 1
T(n) =
T(n-1) + d dla n > 1
Dla n=2, 3, ..., otrzymujemy:
T(1) = c
T(2) = c + d
T(3) = T(2) + d = 2d +c
.......................................
T(n) = T(n-1) + d = (n-1)d +c
T(n) = (n-1)d +c = dn+(c-d) = O(n)+O(1) = O(n)
ASD LJ S
Metody rozwiązywania
c dla n = 1
T(n) =
T(n-1) + d dla n > 1
Dowód poprawności rozwiązania: T(n) = (n-1)d +c
1. Przypadek podstawowy:
T(1)= c
2. Krok indukcyjny:
Założenie: T(n) = (n-1)d+c
Teza: T(n+1) = nd + c
�! T(n+1) = T(n)+d = (n-1)d +c+d = nd + c
�! T(n+1) = nd +d d+c = (n-1)d+c+d = T(n)+d;
Przykład: obliczenie silni: c=0, d=1.
ASD LJ S
2
Metody rozwiązywania
Iterowanie rekurencji (rozwinięcie w sumę).
1 n=1
T(n) =
T(n/2) + d n>1, (n = 2k)
T(n) = T(n/2)+d = (T(n/4)+d )+ d = ((T(n/8) + d) + d) + d =
= ((...(T(n/2k) + k d = T(1) + k d = d log n +1
T(n) = d logn +1
T(n) = O(logn)
Przykład. Wyszukiwanie binarne: d=1, T(n) = logn +1
Dla 2k < n < 2k+1 ze względu na monotonicznośc T(n) zachodzi:
T(2k) < T(n) < T(2k+1)
ASD LJ S
Równania rekurencyjne
Równania typu  dziel i zwyciężaj .
c n=1
T(n) =
aT(n/b) + d(n) n>1, (n = bk)
Równanie rekurencyjne opisuje podział problemu o rozmiarze n na a podproblemów
o rozmiarze n/b każdy, które są niezależnie rozwiązywane, a nastepnie wyniki są
wykorzystywane do wyznaczenia końcowego rozwiązania.
Dodatkowy czas d(n) jest czasem dekompozycji, a następnie łączenia rozwiązań
cząstkowych. Funkcja d(n) - funkcja wiodąca (driving function).
Zakładamy, że problem o rozmiarze n=1 rozwiązywany jest w c jednostkach czasu.
Przykład. Wyszukiwanie binarne: c=1, a=1, b=2, d(n)a"1.
ASD LJ S
3
Równania rekurencyjne
Dziedziną funkcji T(n) są wartości będące potęgami liczby b (n = bk).
c n=1
T(n) =
aT(n/b) + d(n) n>1, (n = bk)
T(n) = aT(n/b) + d(n)
= a ( a(T(n/b2) + d(n/b ) ) + d(n)
= a3 T(n/b3) + a2 d(n/b2) + a d(n/b) + d(n)
................................................................
= ak T(n/bi) + Łj=0k-1 aj d(n/bj)
Dla n = bk, T(n/bk) = T(1) = c, otrzymujemy:
T(n) = cak + Łj=0k-1 aj d(bk-j)
ASD LJ S
Interpretacja rozwiązania
T(n) = cak + Łj=0k-1 aj d(bk-j) = T1(n) + T2(n)
T(n)  rozwiązanie ogólne (general solution)
T1(n) - rozwiązanie jednorodne (homogeneous solution)
T2(n) - rozwiązanie szczegółowe (particular solution)
Rozwiązanie jednorodne.
Dla n = bk:
T1(n) = c ak = c alogbn = c nlogba
Rozwiązanie jednorodne reprezentuje koszt rozwiązania wszystkich podproblemów.
ASD LJ S
4
Rozwiązanie szczegółowe
Rozwiązanie szczegółowe.
T2(n) = Łj=0k-1 aj d(bk-j)
d(bk-j)  funkcja iloczynowa (multiplicative function),
d(bk-j) = d(b)k / d(b)j
T2(n) = Łj=0k-1 aj d(bk-j)
= d(b)k Łj=0k-1(a/d(b))j
= d(b)k ((a/d(b))k  1) / (a/d(b)  1)
= (ak - d(b)k ) / (a / d(b)  1)
dla a `" d(b)
Rozwiązanie szczegółowe reprezentuje koszt podziału problemu na podproblemy i
połączenie rozwiązań cząstkowych w rozwiązanie zasadnicze.
ASD LJ S
Rozwiązanie szczegółowe
Przypadki szczególne:
1. a > d(b): T2(n) = O(ak) = O(nlogba)
2. a < d(b): T2(n) = O(d(b)k) = O (nlogbd(b))
3. a = d(b):
Łj=0k-1 aj d(bk-j) = d(b)k Łj=0k-1(a/d(b))j
= d(b)k Łj=0k-1 1
= d(b)k k
log d(b)
= n logb n
b
T2(n)=O(nlogbd(b) logbn)
ASD LJ S
5
Przypadki szczególne
1. a > d(b): T2(n) = O(ak) = O(nlogba)
Rozwiązania składowe równania wyjściowego są tego samego rzędu i
zdominowane są przez ak = nlogba. Zmniejszanie funkcji d(n) jest tu bezcelowe.
2. a < d(b): T2(n) = O(d(b)k) = O (nlogbd(b))
Rozwiązanie szczegółowe dominuje nad jednorodnym.
Wszelkie ulepszenia T(n) mogą pochodzić od zmniejszenia d(n) i b.
Jeżeli d(n)=ną, wówczas d(b)=bą, logb(bą)=ą. Rozwiązanie szczegółowe jest
rzędu O(ną)=O(d(n)).
3. a = d(b): T2(n) = O(nlogbd(b logbn)
Jeżeli d(n)=ną, to d(b) = bą to rząd rozwiązania wynosi O(d(n) log n).
ASD LJ S
Równania rekurencyjne
Informacje zawarte w równaniu rekurencyjnym:
1. Problem rozmiaru n dzielony jest na a podproblemów, każdy o rozmiarze
n/b.
2. Każdy z a podproblemów jest rozwiązywany rekurencyjnie w czasie T(n/b).
3. Koszt dzielenia problemu oraz łączenia wyników częściowych jest opisany
funkcją d(n).
ASD LJ S
6
Metoda rekurencji uniwersalnej
III. Twierdzenia o rekurencji uniwersalnej.
Niech ae"1, be"1 będą stałymi, zaś d(n) funkcją multiplikatywną.
Rozwiązaniem równania rekurencyjnego postaci:
Ś(1) n=1
T(n) =
aT(n/b) + d(n) n>1, (n = bk)
jest funkcja:
T(n) = Ś(ak) + Łj=0k-1 aj d(bk-j)
log d(b)
Ś( n ) gdy a < d(b)
b
log a
Ś( n logb n ) gdy a = d(b)
T(n) =
b
log a
Ś( n ) gdy a >d(b)
b
ASD LJ S
Metoda rekurencji uniwersalnej
W każdym poniższym przypadku T(1) = 1
1. T(n) = 4 T(n/2) + n
2. T(n) = 4 T(n/2) + n2
3. T(n) = 4 T(n/2) + n3
log4
Dla a=4, b=2, c=1 rozwiązanie jednorodne T1(n) = n = n2 = Ś(n2)
1. d(n) = n, d(b) = 2, a > d(b): T(n) = Ś(n2)
2. d(n) = n2, d(b) = 4 = a: T(n) = Ś(n2 lg n)
3. d(n) = n3, d(b) = d(2) = 8, a < d(b): T(n) = Ś(n3)
ASD LJ S
7
Metoda rekurencji uniwersalnej
Przykład.
1 n=1
T(n) =
8T(n/2) + n3 n>1, (n = 2k)
c=1, a=8, b=2 oraz d(n)=n3.
k -1 k -1
k j k - j 3 k k 3
T (n) = 8 + 8 (2 ) = 8 + 8 (1 + k ) = n (1 + log n)
" " 2
j = 0 j = 0
T(n) = Ś(n3lg n).
ASD LJ S
Metoda rekurencji uniwersalnej
Przykład.
1 n=1
T(n) =
3T(n/2) + 2n"n n>1, (n = 2k)
c=1, a=3, b=2, d(n)=2n2/3, alog2n= nlog2a.
k
3
k-1 k-1
( ) -1
k k
2
j j 8
T(n) = 3k + 2(2k- j )3/ 2 = 3k + 2 8)k ( ) = 3k2 8 = 3k + (3k - 8 )
"3 "( 3
3 3
-1 -1
8
j=0 j=0
8 8
3 3
2
3 / 2
2 2
T (n) = nlg + (nlog - n )
3
-1
8
T(n) = Ś(nlog23).
Funkcja d(n)=2n3/2 nie jest iloczynowa, nie można bezpośrednio skorzystać z
oszacowania wynikającego z tw. o rekurencji uniwersalnej.
ASD LJ S
8
Równania rzędu pierwszego
Równania rekurencyjne typu  jeden krok wstecz (równania rekurencyjne
pierwszego rzędu, first-order).
Ś(1) n=0
T(n) =
aT(n-1) + d(n) n>0
Jeżeli Ś(1)=c, wowczas
c n=0
T(n) =
aT(n-1) + d(n) n>0
Rozwiązanie równania ma postać:
T(n) = can + Łj=1n an-j d(j)
ASD LJ S
Równania rzędu pierwszego
Przykład: n!.
0 n=0
T(n) =
T(n-1) + 1 n>0
T(n) = can + Łj=1n an-j d(j) = Łj=1n 1n-j = n
T(n) = Ś(n)
ASD LJ S
9
Równania rzędu pierwszego
Równanie rekurencyjne typu  jeden krok wstecz .
Przykład (Wieże Hanoi).
0 n = 0
T(n) =
2T(n-1) + 1 n >0
T(n) = can + Łj=1n an-j d(j) = Łj=1n 2n-j = 2n-1 + 2n-2 + + 21 + 20 = (2n-1)/(2-1)
= 2n-1
T(n)=O(2n)
ASD LJ S
Równania rzędu pierwszego
Równanie rekurencyjne typu  jeden krok wstecz .
Przykład:
0 n = 0
T(n) =
3T(n-1) + 2 n >0
T(n) = Łj=1n 3n-j 2
= 2(3n-1 + 3n-2 + ... + 30 ) = 2 Łj=0n-1 3j = 2 (3n-1)/(3-1) = 3n -1
T(n)=O(3n)
ASD LJ S
10
Równania rzędu pierwszego
Przykład:
1 n = 0
T(n) =
2T(n-1) + (-1)n n >0
c=1, a=2, d(n)= (-1)n.
n n n
n- j j n- j
T (n) = 2n + (-1) = 2n + (-1)(n- j)+n+2( j-n) = 2n + (-1)n n- j =
"2 "2 "(-2)
j=1 j=1 j=1
n-1
(-2)n -1 3 1
= 2n + (-1)n j = 2n + (-1)n = 2n + (-1)n
"(-2)
- 2 -1 2 3
j=0
T(n)=O(2n)
ASD LJ S
Równania rzędu pierwszego
Przykład:
1 n = 1
T(n) =
nT(n-1) + n! n >1
T(n) = n!+nT(n-1) = n!+n((n-1)T(n-2)+(n-1)!) = 2n!+n((n-1)T(n-2) =
= 2n!+n((n-1)((n-2)T(n-3)+(n-2)!) = 3n!+n(n-1)(n-2)T(n-3) =
= kn!+n(n-1) (n-k+1)T(n-k) =
..
= (-1)n!+n!T(1) = nn!
T(n)=O(n!).
ASD LJ S
11