12   Délka výpočtu algoritmu
Mimo samotné správnosti výsledku vypočteného zapsaným algoritmem je ještě jedno neméně dUleZite hledisko k posouzení vhodnosti algoritmu k resenízadane Úlohy. Jedna se o čas, který algoritmus stráví výpočtem.
Asi netřeba argumentovat, Ze prehnane dlouha doba odezvy programu je kaZdemu uZivateli nepříjemna. A co třeba v real-time systemech, kde si zdrzení proste nemuzeme dovolit!
Obligatní odpoved' „kupme si rychlejsí počítač" bohuzel není vzdy resením, jak pri pokročilem studiu slozitosti algoritmu sami poznate. Mnohem vetsí potenčial zryčhlení se skryva v algoritmečh samotnyčh a jejičh efektivním navrhu.
Stručný préhléd lékčé
* Délka výpočtu algoritmu, definice na našem deklarativním jazyce.
* Asymptoticke urCení delky výpoCtu - asymptoticke chovaní funkcí.
* Asymptoticke odhady rekurentních vztahu.
Petr Hliněný.  FI MU Brno__I: IB000: Dělka výpočtu algoritmu
12.1   O významu délky výpočtu algoritmu Uvažme deklarativní jazyk Definice 9.1.
Définičé: Delkou výpoCtu výrazu F nad deklarací A rozumíme nejmensí prirozene k takove, že pro nej existuje m € Num pro než F — k m. o
(Když takove m neexistuje, klademe k = oo.)
Jaka je delka vypoCtu nasledujících vyrazu?
* 3 + 4 - 5 * 6 ; otři kroky 3 + 4 - 5 * 6 — 3 + 4 - 30 — 3 + 0 — 3.
* 3 + (5 - 4) * (6 4 2);   tentokrat ctyri kroky
3 +(5 - 4) * (6 4 2) — 3 + 1 * (6 4 2) — 3 + 1 * 3 — 3 + 3 — 6.
* 2010 ; ozadny krok, tj. k = 0.
Petr Hliněný.  FI MU Brn.__Delka výpočtu algoritmu
r.
Příklad 12.1. Pro ukázku uvažme deklaraci A obsahující pouze rovnici
Věta. Pro každé n € N je délka výpočtu výrazu /(n) rovna 4n + 2.c Důkaz povedeme indukcí podle n:
• Ba'ze n = 0. Platí /(0) — if 0 then 0 * /(0 - 1) else 1 fi — 1, čož jsou presne 2 kroký, tj. 4 • 0 + 2.c
• Indukční krok. Nečht n + 1 = k. Pak
/(k) — if k then k * /(k - 1) else 1 fi — k * /(k - 1) — k * /(w),
kde w = k — 1 = n. cTo jsou presne 3 kroký. Podle I.P. je delka výpočtu výrazu /(w) rovna 4n + 2. Pote nasleduje jeste jeden poslední krok výnasobení k. Celkem se provedlo 3 + 4n + 2 + 1 = 4(n + 1) + 2 = 4k + 2
/(x) = if x then x * /(x — 1) else 1 fi .
kroku. c
□
Petr Hliněný,  FI MU Brno
FI: IB000: Delka výpočtu algoritmu
Počítat přesně nebo raději ne?
Jaký ma smysl určení přesného poctu kroků algoritmu při dnešních CPU? Copak jsme dnes schopni jednoznačné říci, jak dlouho jedna instrukce CPU trva? Z druh strany, i kdyZ víme, Ze algoritmus A treba potřebuje 2n kroku výpoctu a algoritmus B třeba potřebuje 3n kroku, je mezi nimi aZ takový rozdíl? Stací, kdyZ B spustíme na dvakrít rychlejsím pocítaci a pomer se hned obrítí. c
Obe tyto prakticky motivovane ívahy nís povedou k pozníní, Ze aditivní a multiplikativní faktory funkce poctu kroku algoritmu jsou vlastne zanedbatelne.
Petr Hliněný,  FI MU Brn.__Dělka výpočtu algoritmu
12.2   Asymptotické značení a odhady funkcí
Zajímá-li nás jen rychlost růstu funkce f (n) v závislosti na n, zaměřujeme se především na tzv. asymptotické chování f při velkých hodnotách n. V popisu f nás tedy nezajímají ani  "drobne cleny", ani konstanty, kterými je f nasobena a ktere jen ovlivnují oselnou hodnotu f (n), ale ne rychlost růstu.
Definice: Necht g : R — K, je dana funkce. Pro funkci f : R — K, píšeme
f e O (g)
pokud existují konstanty A, B > 0 takove, ze
Vn e K+ : f (n) < A • g(n) + B .
V praxi se obvykle (i kdyz matematicky mene presne) píse místo f e O (g) víyraz
f (n) = O(g(n)) .
Znamená to, slovne receno, ze funkce f neroste rychleji nez funkce g. (I kdyz pro malá n třeba muze bát f (n) mnohem vetsí nez g(n).)
Petr Hliněný,  FI MU Brno__I: IB000: Delka výpočtu algoritmu
r.
Definice: Píšeme / € fž(g), neboli
/ (n) = fi( g(n)
pokud g € O(/). Dale píšeme / € 6(g), neboli
/ (n) = G( g(n)
pokud / € O(g) a zaroven / € fž(g), neboli g € O(/).
Výraz /(n) = 6(g(n)) pak cteme jako "funkce / roste stejně rychle jako funkce g". c
ZnaCení: O funkci /(n) říkame:
* / (n) = O(n) je lineární funkce,
* /(n) = 0(n2) je kvadratická funkce,
* /(n) = 0(log n) je logaritmická funkce,
* /(n) = O(nc) pro nejake c > 0 je polynomiální funkce,
* / (n) = ^(cra) pro nejake c > 1 je exponenciální funkce.
'etr Hliněný,  FI MU Brno
FI: IB000: Dělka výpočtu algoritmu
r.
Příklad 12.2. Příklady růstů různých funkcí.
Funkce f (n) = 0(n): pokud n vzroste na dvojnásobek, tak hodnota f (n) taktéž vzroste (zhruba) na dvojnásobek. To platí jak pro funkci f (n) = n, tak
i pro lOOOOOOOOOn nebo n + y/ň, atd.
Funkce f (n) = 0(n2): pokud n vzroste na dvojnasobek, tak hodnota f (n) vzroste (zhruba) na Ctyřnasobek. To platí jak pro funkci f (n) = n2, tak i pro
1000n2 + 1000n nebo n2 - 99999999n - 99999999, atd.
Naopak pro funkci f (n) = 0(2n): pokud n vzroste byť jen o 1, tak hodnota f (n) uz vzroste (zhruba) na dvojnasobek. To je obrovsky rozdíl exponencialních proti polynomialním funkcím.
Pokud vam treba funkce 999999n2 připada velka, jak stojí ve srovnaní s 2n? Zvolme treba n = 1000, kdy 999999n2 = 999999000000 je jeste rozumne
zapsatelne císlo, ale 21000 ~ 10300 byste uz na radek nenapsali. Pro n = 10000
je rozdíl jeste mnohem vyraznejsí!
□
Petr Hliněný,  FI MU Brno
FI: IB000: Dělka výpočtu algoritmu
Příklad 12.3. (opakovaný) Zjistěte, kolik znaků 'x' v závislosti na celočíselné hodnotě n vstupního parametrů n výpíěe následující algoritmus.
Algoritmus 12.4.
foreach   i—1,2,3,...,n-1,n do
foreach   j — 1,2,3,...,i-1,i do vytiskni 'x';
done done c
Zatímco v Lekci 8 jsme trochu zdlouhavě indukcí dokazovali, že výsledkem je \n{n + l) 'x\ nyní si mnohem snadněji odvodíme, že počet 'x' je 6(n2), což je dostaájjící asýmptoticka odpoved' ve vetSine informatických aplikací.
Důkaz: Shora hned odhadneme, že každa z n iterací vnejsího cýklu vytiskne po i < n znaku 'x', takže celkem je nejvýše n2 'x'. Naopak zdola hned vidíme, že posledních n/2 iterací vnejsího cýklu výtiskne i > n/2 znaku 'x', takze celkem je alespoň (n/2) • (n/2) = n2/4 'x'. Z toho podle definice hned výjde asýmptotický odhad 6(n2). □
Petr Hliněný.  FI MU Brn.__Dělka výpočtu algoritmu
12.3   Rekurentní odhady
V tomto oddíle si uvedeme krítky přehled nekterích rekurentních vzorcu, se kterymi se muZete setkat pri resení casove sloZitosti (prevíZne rekurzivních) algoritmu.
Lema 12.5. Nechi a\,...,ak,c > 0 jsou kladné konstanty takové, že a\ + • • • + ak < 1, a funkce T : N —> N spížuje nerovnost
T(n) < T(\am]) + T(\a2n\) + • • • + T(\akn\) + cn.
Pak T(n) = O(n). c
DUkaz: Zvolme e > 0 takove, Ze a\ + • • • + ak < 1 — 2e. Pak pro dostatecne velkí n platí (i se zaokrouhlením nahoru) [ain] + • • • + |~akn] < (1 — e)n, rekneme pro vsechna n > no. Díle zvolme dostatecne velke d > 0 tak, Ze ed > c a zároveň d > max { ^T(n) : n = 1,..., no }.
Díle uZ snadno indukcí podle n dokíZeme T (n) < dn pro vsechna n > 1:
• Pro n < n0 je T (n) < dn podle nasí volby d.
Petr Hliněný,  FI MU Brno__I: IB000: Dělka výpočtu algoritmu
• Predpoklídejme, ze T (n) < dn platí pro vsechna n < ri\, kde n\ > n0 je libovolne. Nyní dokízeme i pro ni
T (ni) < T ([oi nil) + ••• + T (\ak n{\) + cni <
< d • \oinil + • • • + d • \oknil + cni < < d • (1 - e)ni + cni < dni - (ed - c)ni < dni.
□
Léma 12.6. Necht: k > 2 a oi,..., ok, c > 0 jsou kladné konstanty takové, ze oi + • • • + ok = 1, a funkce T : N —> N splňuje nerovnost
T (n) < T (\oinl) + T (\o2nl) + ••• + T (\ok nl) + cn.
Pak T (n) = O(n • log n).
Petr Hliněný.  FI MU Brno
FI: IB000: Dělka výpočtu algoritmu
V obecnosti je známo:
Lema 12.7. Necht a > 1, b > 1 jsou konstanty, f : N — N je funkce a pro funkci T : N — N platí rekurentní vztah
Pak platí
* Je-li f (n) = O(nc) a c < logb a, pak T (n) = O(nlogb a).
* Je-li f (n) = 9(nlogba), pak T (n) = O(nlogba • log n).
* Je-li f (n) = 6(nc) a c> logb a, pak T (n) = O(nc).
Dukaz tohoto obečneho tvrzení přesahuje rozsah naseho predmetu. Vsimnete si, ze nikde ve vyse uvedenyčh reseníčh nevystupují počateční podmínky, tj. hodnoty T(0), T(1), T(2),... - ty jsou "skryte" v nasí O()-notači.
Díle v zípise pro zjednodusení zanedbáváme i nečele čísti argumentu, ktere mohou bíyt zaokrouhleníe.
Petr Hliněný.  FI MU Brno__:I: IB000: Dělka výpočtu algoritmu
Příklad 12.8. Algoritmus merge-sort pro třídění čísel pracuje zhruba následovně:
* Danou posloupnost n Čísel rozdělí na dvě (skoro) poloviny.
* Kaědou polovinu setřídí zvláět za použití rekurentní aplikace merge-sort.
* Tyto dvě uě setěíděne poloviny "slije" (anglicky merge) do jedne setěíděne vyísledníe posloupnosti.
Jakí je celkoví pocet jeho kroku? c
Nečht na vstupuje n čísel. Pri rozdelení na poloviný nam vzniknou podproblemý o velikostech |~n/2] a |_n/2j (pozor na nečele poloviný). Pokud počet kroku výpočtu označ íme T (n), pak rekurzivn ívolan í trvaj íčelkem
T([n/2]) + T(Ln/2j).
Dale potrebujeme c • n kroku (kde c je vhodna konstanta) na slit í obou čast í do výsledneho setřídeneho pole. Celkem tedý výjde
T (n) = T ([n/2]) + T (_n/2j) + cn < T ([n/2]) + T ([n/2]) + cn
a to už je tvar řešený v Lematu 12.6 pro a\ = ci2 = \- Výsledek tedy je
T (n) = O (n • log n). □
Petr Hliněný,  FI MU Brno__:I: IB000: Dělka výpočtu algoritmu
Příklad 12.9. Předpokládejme na vstupu dve „dlouhá" 2m-místná číslá (pro jednoduchost v dekádickem zápise) A á B. Soucin A • B mUěeme rychleji (než školním postupem) vypocitát tákto:
* Císlá si „rozdělíme ná poloviny", tj. ná ctyži m-místná císlá táková, Ze
A = Ai + 10mA2 á B = Bi + 10mB2.
* Rekurzivní áplikácí tehoZ postupu vypocteme tži souciny C1 = A1 • B1,
C2 = A2 • B2 á D = (Ai + A2) • (Bi + B2).
* Dí7e uZ jen secteme (overte si snádno sámi)
A • B = Ci + 10m(D - Ci - C2) + 102mC2 .
Jáky je celkový pocet jeho kroku?
Postupujeme obdobne předchozímu příkladu. Necht T(n) je pocet kroku výpoctu pro vštupn í osla A a B delký nejvýše n = 2m. Tři rekurzivn í volan í pro šouřiný se aplikuj í na císla delek nejvýše m a m +1 (pro (Ai + A2) • (Bi + B2)), takze trvaj í celkem T ([n/2]) + T ([n/2]) + T ([n/2] + 1). nPomocne výpoctu šouřtu a rozd ííu šnadno výkoname v O(n) krocích a pomocne našoben í mocninou 10 je pouhým pošunut ím c íšlic.
Petr Hliněný,  FI MU Brno__:I: IB000: Dělka výpočtu algoritmu
Celkem tedy
T(n) = 2T([n/2]) + T([n/2] + 1) + O(n) < 3T([n/2] + 1) + O(n).
Navíc clen „+1" lze v argumentu asymptoticky zanedbat, a proto podle Lematu 12.7 vypočítáme log2 3 ~ 1.585 > 1 a T(n) = O(nlog23) ~ O(n1.585), coZ je várazne rychlejSí neZ Školní postup v Case O(n2) pro velká n. □
Petr Hliněný.  FI MU Brno__FI: IB000: Delka výpočtu algoritmu