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!
Wyszukiwarka
Podobne podstrony:
nw asd w13
ASD w10%2Cw11
nw asd w6
nw asd w3
nw asd w12
nw asd w8
nw asd w4
nw asd w2
nw asd w5
nw asd w7
nw asd w9
nw asd w2
nw asd w13
więcej podobnych podstron