Treść książki
Przejdź do opcji czytnikaPrzejdź do nawigacjiPrzejdź do informacjiPrzejdź do stopki
22
1.Podstawowezasadyanalizyalgorytmów
Ważnącechąalgorytmujestjegoprostota,zktórejzwyklewynikamniejszywspółczynnik
proporcjonalnościprzyzłożonościobliczeniowejorazłatwośćrealizacji(zaprogramowania).
Szczególniewięcwdwóchprzypadkach:
•program,wktórymjeststosowanynaszalgorytm,mabyćwykonanyrazlubtylkokilka
razy;
•algorytmmabyćstosowanytylkodlamałychrozmiarówdanych;
należywybieraćalgorytmraczejpodkątemjegoprostotyniżmałejzłożonościobliczeniowej
(oczywiścienajlepiejużywaćzawszealgorytmówzarównoprostych,jakiszybkichwsensie
asymptotycznym).
1.2.
Równaniarekurencyjne
Wyznaczeniezłożonościalgorytmusprowadzasięczęstodorozwiązaniarównania
rekurencyjnego.Stosowanesązwykledwiemetody:(1)rozwinięcierównaniadosumy
i(2)znalezieniefunkcjitworzącej.
Metodą2zajmiemysięwnastępnympodrozdziale.Terazpokażemyzastosowaniemetody1
dorozwiązaniatrzechczęstopojawiającychsięrównańrekurencyjnych(coznaczastałą
naturalnądodatnią).
(1)
[
|
4
|
[
T
Tn
()
()
1
=
=
0
T
(
|
L
n
/
2
|
J
)
+
c
dla
n
>
1
(Równanietootrzymujemyjakorównaniezłożonościwtedy,kiedyproblemrozmiarun
sprowadzasiędopodproblemurozmiarupołowęmniejszego).
Rozwiązujemytorównaniedlan=2k(tj.potęgidwójki)istądmożemyjużwnioskować
(zob.zad.1.4),żerządwielkościrozwiązaniaoryginalnegorównaniajesttakisamjakrów-
naniadlapotęgdwójki.
Podstawmywięcn=2k.Wtedy
T(2k)=T(2k-1)+c=T(2k-2)+c+c=T(20)+kc=kc=clogn
Stądwynika,że
T(n)=Θ(logn)
(2)
[
|
4
|
[
T
Tn
()
()
1
=
=
0
T
(
|
L
n
/
2
|
J
)
+
T
(
f
|
n
/
2
1
|
)
+
c
dla
n
>
1
