Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
1.3.Funkcjetworzące
23
(Równanietootrzymujemyjakorównaniezłożonościwtedy,kiedyproblemrozmiarun
sprowadzasiędodwóchpodproblemówrozmiarun/2+stałaliczbadziałań).Podstawmy
więcn=2k.Wtedy
T
()
2
k
=
2
T
(
2
k
−
1
)
+=
c
22
(
T
(
2
k
−
2
)
+
c
)
+=
c
2
2
T
(
2
k
−
2
)
+
2
1
c
+
2
0
c
=
=
2
k
T
(
2
0
)
+
c
(
2
k
−
1
+
2
k
−
2
+
ł
+
2
0
)
=+
0
c
2
21
k
−
−
1
=
cn
(
−
1
)
Stąd,jakpoprzednio,wnioskujemy,że
T(n)=Θ(n)
(3)
[
|
4
|
[
T
Tn
()
()
1
=
=
0
T
(
|
L
n
/
2
|
J
)
+
T
(
f
|
n
/
2
1
|
)
+
cn
dla
n
>
1
(Równanietootrzymamyjakorównaniezłożonościwtedy,kiedyproblemrozmiarunspro-
wadzasiędodwóchpodproblemówrozmiarun/2+liniowaliczbadziałań).Podstawmy
n=2k.Wtedy
T(2k)=2T(2k-1)+c2k=2(2T(2k-2)+c2k-1)+c2k=
=22T(2k-2)+c2k+c2k=2kT(20)+kc2k=0+cnlogn
Mamyzatem
T(n)=Θ(nlogn)
1.3.
Funkcjetworzące
CzasamitrudnowyznaczyćrozwiązanierównaniaT(n)bezpośredniozrównaniareku-
rencyjnego(możenieistniećzwięzływzór).Możnawówczasspróbowaćzastosowaćmetodę
funkcjitworzących,którapoleganaznalezieniufunkcji
Fz
()
=
∑
n
≥
0
Tnz
()
n
nazywanejfunkcjątworzącąT(n),inajejpodstawiewnioskowaćowłasnościachsamej
funkcjiT(n).
Metodętęstosujesięczęstowanalizieprobabilistycznejalgorytmów(dowyznaczeniawar-
tościoczekiwanejiwariancjizmiennejlosowejX
n).Rozważmyfunkcjętworzącąrozkładu
prawdopodobieństwap
nkzmiennejlosowejX
n(zrównańrekurencyjnychnap
nktrudnojest
częstowyznaczyćrozwiązanie):
