Zložitosť algoritrnov^Optimalizácia ^ ^
Zlozitost algoritmov
Q Optimalizácia
Asymptotická zloZitost Príklady
Priemerná a oCakávaná zloZitost Horne a dolne odhady zloZitosti
IB110 Podzim 2010
1
Zložitosť algoritmov^Optimalizácia ^ ^
Zlozitost algoritmov
koreknost algoritmu sama o sebe nezaručuje jeho použiteľnosť
dĺžka výpočtu a jeho pamäťova naročnosť
časova a priesťorova zložitosl!
zložitosl! výpočtu zavisí na vstupnej instančii
zložitosl! algoritmu vyjadrujeme ako funkčiu dlzký vstupnej instančie
IB110 Podzim 2010
2
Zložitosť algoritmov^Optimalizácia ^ ^
Optimalizácia zložitosti algoritmu
■ na úrovni kompilácie
■ programátorská optimalizácia
IB110 Podzim 2010
3
Zložitosť algoritmov^Optimalizácia ^ ^
Príklad 1
Vstup zoznam študentov a počet bodov, ktoré získali v záverečnom teste predmetu IB110 L(1),..., L(N)
Výstup normalizovane body
(1) Najdi maximalny počet bodov, MAX
(2) kazdý bodový zisk vynásob hodnotou 100 a vydel' hodnotou MAX
IB110 Podzim 2010
4
Zložitosť algoritmov^Optimalizácia ^ ^
Implementácia (1) štandartne
(2) for / from 1 to N do L(/) — L(/) x 100/MAX od pre kazde L(/) potrebujeme J nasoben/e a J de/en/e
Optimalizácia (1) štandartne
(2) FAKTOR 4- 100/MAX
(3) for / from 1 to N do L(/) — L(/) x FAKTOR od zlepšenie o cca 50%
IB110 Podzim 2010
5
Zložitosť algoritmov^Optimalizácia ^ ^
Príklad 2
■ vyhladavanie prvkú X v neusporiadanom zozname
■ implementacia pomocou cyklú, v ktorom sa realizujú dva testy: (1) nasli sme X? a (2) prehľadali sme cely zoznam?
■ optimalizacia: na koniec zoznamu pridame prvok X a v cykle test jeme len podmienk (1)
■ po úkoncení cyklú overujeme, ci nújdeny prvok X sa nachadza vo vnútri zoznamú alebo na jeho konci
■ zlepsenie o cca 50%
IB110 Podzim 2010
6
ZIoZitost aIgoritrnov^Asyrriptotická zIoZitost: ^ ^
Zložitosť algoritmov
O
^1 Asymptoticka zlozitost
■ Príklady
■ Priemerna a ocakavaná zlozitost
■ Horne a dolne odhady zlozitosti
IBllO Podzim 2010
ľ
Zložitosť algoritmov;>Asymptotická zložitosť !3> ^
Otázky
■ je zlepšenie o 50% (60%, 90% ...) dostačujúce?
■ ako charakterizoval! zloZitost algoritmu? ako porovnal! zloZitost! dvoch algoritmov?
zložitosť algoritmu ako funkcia dĺžky vstupnej inštancie
zložitosť v najhoršom prípade
asymptotická zložitost, O-notacia
IB110 Podzim 2010
8
Zložitosť algoritmov ^Asymptotická zložitosť !3> ^
Asymptotická zložitosť
■ jednoduchá charakterizácia efektivity algoritmu
■ umoZňuje porovnal! relatívnu efektivitu rôznych algoritmov
■ charakterizuje, ako rastie zloZitost algoritmu s rastúcou dlZkou vstupnej instancie
O-notúcia
Symbolom O(g(n)) oznacujeme mnozinu fukciít.z.
O(g(n)) = {f(n) |   existuje kladná konstanta c a no
take, že 0 < f (n) < cg (n) pre vsetky n > no}.
Rovnost! f (n) = O(g (n)) vyjadruje, ze f (n) je prvkom mnoziny O(g (n)).
IB110 Podzim 2010
9
Zložitosť algoritmov ^Asymptotická zložitosť !3> !3>
Robustnost: O-notácie
Fakt
O-notacia zakrýva konštantné faktory
■ Casova zloZitost algoritmu jé relativný pojem
■ zloZitost jé rélativna voCi fixovanej mnoZine élémentarnych inštrukcii
■ kaZdý programovac i jazyk resp. kompilator moZé mal; inU mnoZinu élementarnych instrukci i
■ pokial' pouZivaju standartne instrukcie, tak rozdiel v casovej zloZitosti je prave o konstantny faktor
■ O-notacia je invariantna voci takymto implementacnym detailom
Nevyhoda O-notacie: skryte konstanty, hranicna hodnota hq
IB110 Podzim 2010
10
ZloZitost: algoritmov ;S=-Asymptoticka zloZitost: ^ Príklady ^
Binárne vyhľadávanie
Binarne vyhl'adavanie polozky Y v telefónnom zozname s N polozkami X1, X2,..., XN pre N = 1000000
linearne vyhl'adavanie az 1 000 000 porovnaní zlozitost O(N)
binárne vyhl'adavanie postup: v prvom kroku porovnaj Y s X500000
podl'a vysledku porovnaj v druhom kroku Y bud' s X250000 alebo s X750000
v najhorsom prípade 20 porovnaná zlozitost O(log2(N))
PreCo?
sme ako zlozitost! vyhladavania sme uvazovali len poCet porovnaná?
IB110 Podzim 2010
11
Zložitosl: algoritmov;>Asymptoticka zlozitost: ^ Príklady ^
Bubblésort
1 proceduře Bubblesort(A, n)
2 for i = 1 to n — 1 do
3 for j = 1 to n — i do
4 if A j ] > Aj + 1] then vymeň A j] s Aj + 1] i
5 od
6 od
riadok 4 for cyklús 3 -for cyklús 2 -
cas
cas O(n — i)
O(n(n — 1) — £"L-1 i) = O(n2)
celkovú casovú zlozitost! je O(n2)
IB110 Podzim 2010
12
Zložitosť algoritmovAsymptotická zložitosť !3> Príklady ^
Vnorené cykly
1 r — 0
2 for i = 1 to n do
3 for j = 1 to i do
4 for k = j to i + j do
5 r — r + 1
6 od
7 od
8 od
(i + j) — j + 1 = i + 1 priradení
i opakovaní cyklu 4-6, tj. i (i + 1) = i2 + i priradení
n — 1 opakovaní cyklu 3-7, tj. ^"Tj1 i2 + i priradení
y1 i 2 + i =  (n — 1)n(2n — 1) + (n — 1)n =  n3 — n = ^(„S)
/=1
IB110 Podzim 2010
13
Zložitosť algoritmov^Asymptotická zložitosť !3> Príklady ^
Maximálny a minimálny prvok
Problém nájdenia maximálneho a minimálneho prvku postupnosti S[1..n]. Zložitostné kritérium - počet porovnaní prvkov.
max — S [1]
for i from 2 to n do
if S [i] > max then max — S [i] i
od
Minimum najdeme medži žvySnymi n — 1 prvkami podobne. Celkove (n — 1) + (n — 2) porovnaní.
IB110 Podzim 2010
14
Zložitosť algoritmov;§=-Asymptotická zložitosť !3> Príklady ^
Maximálny a minimálny prvok
Prístup Rozdel' a panuj
| pole rozdel' na dve (rovnako vel'ke) podpostunosti
^ najdi minimum a maximum oboch podpostupností
^ maximálny prvok postupnosti je vacsí z maximainych prvkov podpostupností; podobne minimalny prvok
function Maxmin(x, y)
if y — x < 1 then return (max(S [x], S [y]), min(S [x], S [y])) else (max 1, m/n1) — Maxmin(x, [(x + y)/2j)
(max2, m/n2) — Maxmin( [(x + y)/2j +1, y) return (max(max 1, max2) min(m/n1, m/n2))
fi
IB110 Podzim 2010
15
Zložitosť algoritmov ;S=-Asyrnptoticka zložitosť !3> Príklady ^
Maximálny a minimálny prvok
Zlozitost: (počet porovnaní)
T(n) = í1 pre " = 2
\T(Ln/2J)+ T(ľn/21) + 2   pre n > 2
Indukciou k n overíme, ze T (n) < 5 n — 2. | Pre n = 2 platí f • 2 — 2 > 1 = T(2).
1 Predpokladajme platnost! nerovnosti pre vsetky hodnoty 2 < i < n, dokazeme jej platnost! pre n.
T (n) = T ([n/2j) + T ([n/21) + 2 indukčny predp.
< 3 Ln/2J — 2 + 5 [n/21— 2 + 2 = 5 n — 2
IB110 Podzim 2010
16
Zložitosť algoritmov^Asymptotická zložitosť !3> Priemerná a očakávaná zložitosť ^
Priemerná a očakávaná zložitosť
t priemer zložitostí výpočtov na všetkých vstupoch danej dlžký
Quicksort - zlozitost v najhoršom prípade je O(n2), priemerná zlozitost je O(n log n)
zloZitost! jednotlivých výpočtov je vážena frekvenciou výskýtu príslušných vstupných inštancií
Výhodý: presnejsia informacia o efektivite algoritmu
v prípade očakávanej zložitosti je relevancia voči aplikačnej oblasti
Nevýhodý: obtiažna analýza
v prípade očakávanej zložitosti nutnost poznat presnu frekvenciu vstupních inštancií
IB110 Podzim 2010
17
Zložitost algoritmov;>Asyrriptoticka zložitost !3> Horne a dolne odhady zložitosti ^
Horné a dolné odhady zložitosti
■ v najlepsom prípade
■ v najhorsom prípade
■ priemernú zlozitost
■ ocakavanú zlozitost
■ dolny odhad zlozitosti problemú
■ horny odhad zlozitosti problemú — zlozitost! konkríetneho algoritm   pre problíem
■ zlozitost! problemú
IB110 Podzim 2010
18
Zložitost algoritmovAsymptotická zložitost !3> Horne a dolne odhady zložitosti ^
Techniky
Informacna metoda riesenie problemu v sebe obsahuje iste mnoZstvo
informacie a v kaZdom kroku vypoctu sme schopn i urciť len cast tejto informacie (násobenie matíc, cesta v grafe, triedenie)
Metoda sporu Varianta A: za predpokladu, Ze algoritmus ma zloZitost mensiu neZ uvaZovanu hranicu, vieme skonstruovat vstup, na ktorom neda korektne riesenie. Varianta B: za predpokladu, Ze algoritmus najde vZdy korektne riesenie, vieme skonstruoval! vstup, pre ktory zloZitost! vypoctu presiahne uvaZovanu hranicu.
Redukcia
IB110 Podžim 2010
19
Zložitost algoritmovAsymptotická zložitost !3> Horne a dolne odhady zložitosti ^
Príklad: maximálny prvok postupnosti
Dolny odhad
Nech algoritmus A je algoritmus založený na porovnávaní prvkov a nech A rieši problém maximálneho prvku. Potom A musí na každom vstupe vykonat, aspon n — 1 porovnaní.
Dokaz
Nech x = (xi,..., xn) je vstup dlZky n, na ktorom A vykona menej neZ
n — 1 porovnaní a nech xr je maximalny prvok v x.
Potom v x musí existoval! prvok xp taky, Ze p = r a v priebehu vypoctu
xp nebol porovnavany so Žiadnym prvkom väcsím neZ on sam. Existencia
takeho prvku plynie z poctu vykonaných porovnaní.
Ak v x zmeníme hodnotu prvku xp na xr + 1, tak A urcí ako maximalny
prvok xr - spor.
IB110 Podžim 2010
20
Zložitost algoritmov;>Asyrriptoticka zložitost !3> Horne a dolne odhady zložitosti ^
Príklad: vyhľadávanie v telefónnom zozname
binárny strom a jeho hlbka
IB110 Podzim 2010
21
Zložitosť algoritmovAsymptotická zložitosť !3> Horné a dolné odhady zložitosti ^
Výzkum v oblasti zložitosti problémov
optimalizácia dátových štruktúr
dolné odhadý zloZitosti a dokaz optimalitý
priestorová zloZitost
vztah medzi priestorovou a Časovou zlozitostou
IB110 Podzim 2010
22