1
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
2
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
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.
Dowód poprawności rozwiązania: T(n) = (n-1)d +c
ASD
LJ
S
3
Metody rozwiązywania
Iterowanie rekurencji (rozwinięcie w sumę).
1
n=1
T(n) =
T(n/2) + d n>1, (n = 2
k
)
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)
Dla 2
k
< n < 2
k+1
ze względu na monotonicznośc T(n) zachodzi:
T(2
k
) < T(n) < T(2
k+1
)
ASD
LJ
S
Przykład. Wyszukiwanie binarne: d=1, T(n) = logn +1
Równania rekurencyjne
Równania typu „dziel i zwyciężaj”
.
c
n=1
T(n) =
aT(n/b) + d(n) n>1, (n = b
k
)
ASD
LJ
S
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)
≡1.
4
Równania rekurencyjne
T(n)
= aT(n/b) + d(n)
= a ( a(T(n/b
2
) + d(n/b ) ) + d(n)
= a
3
T(n/b
3
) + a
2
d(n/b
2
) + a d(n/b) + d(n)
................................................................
= a
k
T(n/b
i
) +
Σ
j=0
k-1
a
j
d(n/b
j
)
Dla n = b
k
, T(n/b
k
) = T(1) = c, otrzymujemy:
T(n) = ca
k
+
Σ
j=0
k-1
a
j
d(b
k-j
)
c
n=1
T(n) =
aT(n/b) + d(n) n>1, (n = b
k
)
ASD
LJ
S
Dziedziną funkcji T(n) są wartości będące potęgami liczby b (n = b
k
).
Interpretacja rozwiązania
T(n) – rozwiązanie ogólne (
general solution
)
T
1
(n) - rozwiązanie jednorodne (
homogeneous solution
)
T
2
(n) - rozwiązanie szczegółowe (
particular solution
)
T(n) = ca
k
+
Σ
j=0
k-1
a
j
d(b
k-j
) = T
1
(n) + T
2
(n)
ASD
LJ
S
Rozwiązanie jednorodne.
Dla n = b
k
:
T
1
(n) = c a
k
= c a
log
b
n
= c n
log
b
a
Rozwiązanie jednorodne reprezentuje koszt rozwiązania wszystkich podproblemów.
5
Rozwiązanie szczegółowe
Rozwiązanie szczegółowe.
ASD
LJ
S
T
2
(n) =
Σ
j=0
k-1
a
j
d(b
k-j
)
d(b
k-j
) – funkcja iloczynowa (
multiplicative function
),
d(b
k-j
) = d(b)
k
/ d(b)
j
T
2
(n) =
Σ
j=0
k-1
a
j
d(b
k-j
)
= d(b)
k
Σ
j=0
k-1
(a/d(b))
j
= d(b)
k
((a/d(b))
k
–1) / (a/d(b) –1)
= (a
k
- 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.
Rozwiązanie szczegółowe
1.
a > d(b):
T
2
(n) = O(a
k
) = O(n
log
b
a
)
2.
a < d(b): T
2
(n) = O(d(b)
k
) = O (n
log
b
d(b)
)
3.
a = d(b):
Σ
j=0
k-1
a
j
d(b
k-j
) = d(b)
k
Σ
j=0
k-1
(a/d(b))
j
= d(b)
k
Σ
j=0
k-1
1
= d(b)
k
k
= n
log
b
d(b)
log
b
n
T
2
(n)=O(n
log
b
d(b)
log
b
n)
Przypadki szczególne:
ASD
LJ
S
6
Przypadki szczególne
1.
a > d(b):
T
2
(n) = O(a
k
) = O(n
log
b
a
)
ASD
LJ
S
Rozwiązania składowe równania wyjściowego są tego samego rzędu i
zdominowane są przez a
k
= n
log
b
a
. Zmniejszanie funkcji d(n) jest tu bezcelowe.
2.
a < d(b):
T
2
(n) = O(d(b)
k
) = O (n
log
b
d(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
α
, log
b
(b
α
)=
α. Rozwiązanie szczegółowe jest
rzędu O(n
α
)=O(d(n)).
3.
a = d(b): T
2
(n) = O(n
log
b
d(b
log
b
n)
Jeżeli d(n)=n
α
, to d(b) = b
α
to rząd rozwiązania wynosi O(d(n) log n).
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
7
Metoda rekurencji uniwersalnej
Niech a
≥1, b≥1 będą stałymi, zaś d(n) funkcją multiplikatywną.
Rozwiązaniem równania rekurencyjnego postaci:
jest funkcja:
Θ(1)
n=1
T(n) =
aT(n/b) + d(n) n>1, (n = b
k
)
T(n) =
Θ(a
k
) +
Σ
j=0
k-1
a
j
d(b
k-j
)
T(n) =
Θ( n
log
b
d(b)
)
gdy a < d(b)
Θ( n
log
b
a
log
b
n )
gdy a = d(b)
Θ( n
log
b
a
)
gdy a >d(b)
III. Twierdzenia o rekurencji uniwersalnej.
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) + n
2
3.
T(n) = 4 T(n/2) + n
3
Dla a=4, b=2, c=1 rozwiązanie jednorodne T
1
(n) = n
log4
= n
2
=
Θ(n
2
)
1.
d(n) = n, d(b) = 2, a > d(b):
T(n) =
Θ(n
2
)
2.
d(n) = n
2
, d(b) = 4 = a:
T(n) =
Θ(n
2
lg n)
3.
d(n) = n
3
, d(b) = d(2) = 8, a < d(b):
T(n) =
Θ(n
3
)
ASD
LJ
S
8
Metoda rekurencji uniwersalnej
Przykład.
ASD
LJ
S
1
n=1
T(n) =
8T(n/2) + n
3
n>1, (n = 2
k
)
)
log
1
(
)
1
(
8
8
)
2
(
8
8
)
(
2
3
1
0
3
1
0
n
n
k
n
T
k
j
k
k
j
k
k
j
j
k
+
=
+
+
=
+
=
∑
∑
−
=
−
−
=
c=1, a=8, b=2 oraz d(n)=n
3
.
T(n) =
Θ(n
3
lg n).
Metoda rekurencji uniwersalnej
Przykład.
ASD
LJ
S
1
n=1
T(n)
=
3T(n/2) + 2n
√n
n>1, (n = 2
k
)
c=1, a=3, b=2, d(n)=2n
2/3
, a
log
2
n
= n
log
2
a
.
T(n) =
Θ(n
log
2
3
).
( )
)
8
3
(
1
2
3
1
1
8
2
3
)
8
3
(
)
8
(
2
3
)
2
(
2
3
3
)
(
8
3
8
3
8
3
1
0
2
/
3
1
0
k
k
k
k
k
k
j
k
k
j
k
j
k
k
j
j
k
n
T
−
−
+
=
−
−
=
+
=
+
=
∑
∑
−
=
−
−
=
)
log
(
1
2
lg
)
(
2
/
3
3
8
3
3
2
2
n
n
n
n
T
−
−
+
=
Funkcja d(n)=2n
3/2
nie jest iloczynowa, nie można bezpośrednio skorzystać z
oszacowania wynikającego z tw. o rekurencji uniwersalnej.
9
Równania rzędu pierwszego
Równania rekurencyjne typu „jeden krok wstecz” (równania rekurencyjne
pierwszego rzędu,
first-order
).
c
n=0
T(n) =
aT(n-1) + d(n)
n>0
T(n) = ca
n
+ Σ
j=1
n
a
n-j
d(j)
ASD
LJ
S
Θ(1)
n=0
T(n) =
aT(n-1) + d(n)
n>0
Rozwiązanie równania ma postać:
Jeżeli
Θ(1)=c
,
wowczas
Równania rzędu pierwszego
Przykład: n!.
0
n=0
T(n) =
T(n-1) + 1
n>0
T(n) = ca
n
+
Σ
j=1
n
a
n-j
d(j) =
Σ
j=1
n
1
n-j
= n
T(n) =
Θ(n)
ASD
LJ
S
10
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) = ca
n
+
Σ
j=1
n
a
n-j
d(j) =
Σ
j=1
n
2
n-j
= 2
n-1
+ 2
n-2
+ H + 2
1
+ 2
0
= (2
n
-1)/(2-1)
= 2
n
-1
T(n)=O(2
n
)
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=1
n
3
n-j
2
= 2(3
n-1
+ 3
n-2
+ ... + 3
0
) = 2
Σ
j=0
n-1
3
j
= 2 (3
n
-1)/(3-1) = 3
n
-1
ASD
LJ
S
T(n)=O(3
n
)
11
Równania rzędu pierwszego
Przykład:
1
n = 0
T(n) =
2T(n-1) + (-1)
n
n >0
ASD
LJ
S
T(n)=O(2
n
)
c=1, a=2, d(n)= (-1)
n
.
n
n
n
n
n
n
j
j
n
n
n
j
j
n
n
n
n
j
n
j
n
n
j
j
n
n
j
n
j
j
n
n
n
T
)
1
(
3
1
2
2
3
1
2
1
)
2
(
)
1
(
2
)
2
(
)
1
(
2
)
2
(
)
1
(
2
)
1
(
2
2
)
1
(
2
2
)
(
1
0
1
)
(
2
)
(
1
1
−
+
=
−
−
−
−
−
+
=
−
−
+
=
=
−
−
+
=
−
+
=
−
+
=
∑
∑
∑
∑
−
=
=
−
−
+
+
−
=
−
=
−
Równania rzędu pierwszego
Przykład:
1
n = 1
T(n) =
nT(n-1) + n!
n >1
ASD
LJ
S
T(n)=O(n!).
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) =
HHHHH
= kn!+n(n-1)H(n-k+1)T(n-k) =
HHHH..
= (-1)n!+n!T(1) = nn!