' $' & $ %Petr Hliněný, FI MU Brno 1 IB000 "Úv. Inf.": Délka výpočtu algoritmu 12 Délka výpočtu algoritmu12 Délka výpočtu algoritmu Mimo samotné správnosti výsledku vypočteného zapsaným algoritmem je ještě jedno neméně důležité hledisko k posouzení vhodnosti algoritmu k řešení zadané úlohy. Jedná se o čas, který algoritmus stráví výpočtem. Asi netřeba argumentovat, že přehnaně dlouhá doba odezvy programu je každému uživateli nepříjemná. A co třeba v real-time systémech, kde si zdržení prostě nemůžeme dovolit! Obligátní odpověď ,,kupme si rychlejší počítač bohužel není vždy řešením, jak při pokročilém studiu složitosti algoritmů sami poznáte. Mnohem větší potenciál zrychlení se skrývá v algoritmech samotných a jejich efektivním návrhu. Stručný přehled lekce * Délka výpočtu algoritmu, definice na našem deklarativním jazyce. * Asymptotické určení délky výpočtu ­ asymptotické chování funkcí. * Asymptotické odhady rekurentních vztahů. ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Délka výpočtu algoritmu 12.1 O významu délky výpočtu algoritmu12.1 O významu délky výpočtu algoritmu Uvažme deklarativní jazyk Definice Definice: Délkou výpočtu výrazu F nad deklarací rozumíme nejmenší přiro- zené k takové, že pro něj existuje m Num pro něž F k m. ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Délka výpočtu algoritmu 12.1 O významu délky výpočtu algoritmu12.1 O významu délky výpočtu algoritmu Uvažme deklarativní jazyk Definice Definice: Délkou výpočtu výrazu F nad deklarací rozumíme nejmenší přiro- zené k takové, že pro něj existuje m Num pro něž F k m. (Když takové m neexistuje, klademe k = .) Jaká je délka výpočtu následujících výrazů? 3 + 4 - 5 6 ; ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Délka výpočtu algoritmu 12.1 O významu délky výpočtu algoritmu12.1 O významu délky výpočtu algoritmu Uvažme deklarativní jazyk Definice Definice: Délkou výpočtu výrazu F nad deklarací rozumíme nejmenší přiro- zené k takové, že pro něj existuje m Num pro něž F k m. (Když takové m neexistuje, klademe k = .) Jaká je délka výpočtu následujících výrazů? 3 + 4 - 5 6 ; Tři kroky 3 + 4 - 5 6 3 + 4 - 30 3 + 0 3. 3 + (5 - 4) (6 ÷ 2) ; ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Délka výpočtu algoritmu 12.1 O významu délky výpočtu algoritmu12.1 O významu délky výpočtu algoritmu Uvažme deklarativní jazyk Definice Definice: Délkou výpočtu výrazu F nad deklarací rozumíme nejmenší přiro- zené k takové, že pro něj existuje m Num pro něž F k m. (Když takové m neexistuje, klademe k = .) Jaká je délka výpočtu následujících výrazů? 3 + 4 - 5 6 ; Tři kroky 3 + 4 - 5 6 3 + 4 - 30 3 + 0 3. 3 + (5 - 4) (6 ÷ 2) ; Tentokrát čtyři kroky 3 + (5 - 4) (6 ÷ 2) 3 + 1 (6 ÷ 2) 3 + 1 3 3 + 3 6. 2007 ; ' $' & $ %Petr Hliněný, FI MU Brno 2 IB000 "Úv. Inf.": Délka výpočtu algoritmu 12.1 O významu délky výpočtu algoritmu12.1 O významu délky výpočtu algoritmu Uvažme deklarativní jazyk Definice Definice: Délkou výpočtu výrazu F nad deklarací rozumíme nejmenší přiro- zené k takové, že pro něj existuje m Num pro něž F k m. (Když takové m neexistuje, klademe k = .) Jaká je délka výpočtu následujících výrazů? 3 + 4 - 5 6 ; Tři kroky 3 + 4 - 5 6 3 + 4 - 30 3 + 0 3. 3 + (5 - 4) (6 ÷ 2) ; Tentokrát čtyři kroky 3 + (5 - 4) (6 ÷ 2) 3 + 1 (6 ÷ 2) 3 + 1 3 3 + 3 6. 2007 ; Žádný krok, tj. k = 0. ' $' & $ %Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.1. Pro ukázku uvažme deklaraci obsahující pouze rovnici f(x) = if x then x f(x - 1) else 1 . Věta. Pro každé n N je délka výpočtu výrazu f(n) rovna 4n + 2. ' $' & $ %Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.1. Pro ukázku uvažme deklaraci obsahující pouze rovnici f(x) = if x then x f(x - 1) else 1 . Věta. Pro každé n N je délka výpočtu výrazu f(n) rovna 4n + 2. Důkaz povedeme indukcí podle n: ˇ Báze n = 0. Platí f(0) if 0 then 0 f(0 - 1) else 1 1, což jsou přesně 2 kroky, tj. 4 0 + 2. ' $' & $ %Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.1. Pro ukázku uvažme deklaraci obsahující pouze rovnici f(x) = if x then x f(x - 1) else 1 . Věta. Pro každé n N je délka výpočtu výrazu f(n) rovna 4n + 2. Důkaz povedeme indukcí podle n: ˇ Báze n = 0. Platí f(0) if 0 then 0 f(0 - 1) else 1 1, což jsou přesně 2 kroky, tj. 4 0 + 2. ˇ Indukční krok. Nechť n + 1 k. Pak f(k) if k then k f(k - 1) else 1 k f(k - 1) k f(w) , kde w k - 1 = n. ' $' & $ %Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.1. Pro ukázku uvažme deklaraci obsahující pouze rovnici f(x) = if x then x f(x - 1) else 1 . Věta. Pro každé n N je délka výpočtu výrazu f(n) rovna 4n + 2. Důkaz povedeme indukcí podle n: ˇ Báze n = 0. Platí f(0) if 0 then 0 f(0 - 1) else 1 1, což jsou přesně 2 kroky, tj. 4 0 + 2. ˇ Indukční krok. Nechť n + 1 k. Pak f(k) if k then k f(k - 1) else 1 k f(k - 1) k f(w) , kde w k - 1 = n. To jsou přesně 3 kroky. Podle I.P. je délka výpočtu výrazu f(w) rovna 4n + 2. Poté následuje ještě jeden poslední krok vyná- sobení k. Celkem se provedlo 3+4n+2+1 = 4(n+1)+2 = 4k +2 kroků. ' $' & $ %Petr Hliněný, FI MU Brno 3 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.1. Pro ukázku uvažme deklaraci obsahující pouze rovnici f(x) = if x then x f(x - 1) else 1 . Věta. Pro každé n N je délka výpočtu výrazu f(n) rovna 4n + 2. Důkaz povedeme indukcí podle n: ˇ Báze n = 0. Platí f(0) if 0 then 0 f(0 - 1) else 1 1, což jsou přesně 2 kroky, tj. 4 0 + 2. ˇ Indukční krok. Nechť n + 1 k. Pak f(k) if k then k f(k - 1) else 1 k f(k - 1) k f(w) , kde w k - 1 = n. To jsou přesně 3 kroky. Podle I.P. je délka výpočtu výrazu f(w) rovna 4n + 2. Poté následuje ještě jeden poslední krok vyná- sobení k. Celkem se provedlo 3+4n+2+1 = 4(n+1)+2 = 4k +2 kroků. 2 ' $' & $ %Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Délka výpočtu algoritmu Počítat přesně nebo raději ne? Jaký má smysl určení přesného počtu kroků algoritmu při dnešních CPU? Copak jsme dnes schopni jednoznačně říci, jak dlouho jedna instrukce CPU trvá? Z druh strany, i když víme, že algoritmus A třeba potřebuje 2n kroků výpočtu a algoritmus B třeba potřebuje 3n kroků, je mezi nimi až takový rozdíl? Stačí, když B spustíme na dvakrát rychlejším počítači a poměr se hned obrátí. ' $' & $ %Petr Hliněný, FI MU Brno 4 IB000 "Úv. Inf.": Délka výpočtu algoritmu Počítat přesně nebo raději ne? Jaký má smysl určení přesného počtu kroků algoritmu při dnešních CPU? Copak jsme dnes schopni jednoznačně říci, jak dlouho jedna instrukce CPU trvá? Z druh strany, i když víme, že algoritmus A třeba potřebuje 2n kroků výpočtu a algoritmus B třeba potřebuje 3n kroků, je mezi nimi až takový rozdíl? Stačí, když B spustíme na dvakrát rychlejším počítači a poměr se hned obrátí. Obě tyto prakticky motivované úvahy nás povedou k poznání, že aditivní a multiplikativní faktory funkce počtu kroků algoritmu jsou vlastně zanedbatelné. ' $' & $ %Petr Hliněný, FI MU Brno 5 IB000 "Úv. Inf.": Délka výpočtu algoritmu 12.2 Asymptotické značení a odhady funkcí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 "drobné členy", ani konstanty, kterými je f násobena a které jen ovlivňují číselnou hodnotu f(n), ale ne rychlost růstu. Definice: Nechť g : N N je daná funkce. Pro funkci f : N N píšeme f O(g) pokud existují konstanty A, B > 0 takové, že n N : f(n) A g(n) + B . V praxi se obvykle (i když matematicky méně přesně) píše místo f O(g) výraz f(n) = O(g(n)) . Znamená to, slovně řečeno, že funkce f neroste rychleji než funkce g. (I když pro malá n třeba může být f(n) mnohem větší než g(n).) ' $' & $ %Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Délka výpočtu algoritmu Definice: Píšeme f (g), neboli f(n) = (g(n)) , pokud g O(f). Dále píšeme f (g), neboli f(n) = (g(n)) , pokud f O(g) a zároveň f (g), neboli g O(f). Výraz f(n) = (g(n)) pak čteme jako "funkce f roste stejně rychle jako funkce g". ' $' & $ %Petr Hliněný, FI MU Brno 6 IB000 "Úv. Inf.": Délka výpočtu algoritmu Definice: Píšeme f (g), neboli f(n) = (g(n)) , pokud g O(f). Dále píšeme f (g), neboli f(n) = (g(n)) , pokud f O(g) a zároveň f (g), neboli g O(f). Výraz f(n) = (g(n)) pak čteme jako "funkce f roste stejně rychle jako funkce g". Značení: O funkci f(n) říkáme: f(n) = (n) je lineární funkce, f(n) = (n2) je kvadratická funkce, f(n) = (log n) je logaritmická funkce, f(n) = O(nc) pro nějaké c > 0 je polynomiální funkce, f(n) = (cn) pro nějaké c > 1 je exponenciální funkce. ' $' & $ %Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.2. (opakovaný) Zjistěte, kolik znaků 'x' v závislosti na celočíselné hodnotě n vstupního parametru n vypíše následující algoritmus. Algoritmus 12.3. for i 1,2,3,...,n-1,n do for j 1,2,3,...,i-1,i do vytiskni 'x'; done done ' $' & $ %Petr Hliněný, FI MU Brno 7 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.2. (opakovaný) Zjistěte, kolik znaků 'x' v závislosti na celočíselné hodnotě n vstupního parametru n vypíše následující algoritmus. Algoritmus 12.3. for i 1,2,3,...,n-1,n do for j 1,2,3,...,i-1,i do vytiskni 'x'; done done Zatímco v Lekci 8 jsme trochu zdlouhavě indukcí dokazovali, že výsledkem je 1 2 n(n+1) 'x', nyní si mnohem snadněji odvodíme, že počet 'x' je (n2), což je dostačující asymptotická odpověď ve většině informatických aplikací. Důkaz: Shora hned odhadneme, že každá z n iterací vnějšího cyklu vytiskne i n znaků 'x', takže celkem je nejvýše n2 'x'. Naopak zdola hned vidíme, že posledních n/2 iterací vnějšího cyklu vytiskne i n/2 znaků 'x', takže celkem je alespoň (n/2) (n/2) = n2/4 'x'. Z toho podle definice hned vyjde asymptotický odhad (n2). 2 ' $' & $ %Petr Hliněný, FI MU Brno 8 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.4. Příklady růstů různých funkcí. Funkce f(n) = (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 1000000000n nebo n + n, atd. Funkce f(n) = (n2): pokud n vzroste na dvojnásobek, tak hodnota f(n) vzroste (zhruba) na čtyřnásobek. To platí jak pro funkci f(n) = n2, tak i pro 1000n2 + 1000n nebo n2 - 99999999n - 99999999, atd. Naopak pro funkci f(n) = (2n): pokud n vzroste byť jen o 1, tak hodnota f(n) už vzroste (zhruba) na dvojnásobek. To je obrovský rozdíl exponenciálních proti polynomiálním funkcím. Pokud vám třeba funkce 999999n2 připadá velká, jak stojí ve srovnání s 2n? Zvolme třeba n = 1000, kdy 999999n2 = 999999000000 je ještě rozumně zapsatelné číslo, ale 21000 10300 byste už na řádek nenapsali. Pro n = 10000 je rozdíl ještě mnohem výraznější! 2 ' $' & $ %Petr Hliněný, FI MU Brno 9 IB000 "Úv. Inf.": Délka výpočtu algoritmu Rekurentní odhady V tomto oddíle si uvedeme krátký přehled některých rekurentních vzorců, se kterými se můžete setkat při řešení časové složitosti (převážně rekurzivních) algoritmů. Lema 12.5. Nechť a1, . . . , ak, c > 0 jsou kladné konstanty takové, že a1 + . . . + ak < 1, a funkce T : N N splňuje nerovnost T(n) T( a1n ) + T( a2n ) + . . . + T( akn ) + cn . Pak T(n) = O(n). Důkaz: Zvolme > 0 takové, že a1 + . . . + ak < 1 - 2. Pak pro dostatečně velká n platí (i se zaokrouhlením nahoru) a1n + . . . + akn (1 - )n, řekněme pro všechna n n0. Dále zvolme dostatečně velké d > 0 tak, že d > c a zároveň d > max { 1 nT(n) : n = 1, . . . , n0}. Dále už snadno indukcí podle n dokážeme T(n) dn pro všechna n 1: ˇ Pro n n0 je T(n) dn podle naší volby d. ' $' & $ %Petr Hliněný, FI MU Brno 10 IB000 "Úv. Inf.": Délka výpočtu algoritmu ˇ Předpokládejme, že T(n) dn platí pro všechna n < n1, kde n1 > n0 je libovolné. Nyní dokážeme i pro n1 T(n1) T( a1n1 ) + . . . + T( akn1 ) + cn1 d a1n1 + . . . + d akn1 + cn1 d (1 - )n1 + cn1 dn1 - (d - c)n1 dn1 . 2 Lema 12.6. Nechť k 2 a a1, . . . , ak, c > 0 jsou kladné konstanty takové, že a1 + . . . + ak = 1, a funkce T : N N splňuje nerovnost T(n) T( a1n ) + T( a2n ) + . . . + T( akn ) + cn . Pak T(n) = O(n log n). ' $' & $ %Petr Hliněný, FI MU Brno 11 IB000 "Úv. Inf.": Délka výpočtu algoritmu V obecnosti je známo: Lema 12.7. Nechť a 1, b > 1 jsou konstanty, f : N N je funkce a pro funkci T : N N platí rekurentní vztah T(n) a T n b + f(n) . Pak platí: Je-li f(n) = O(nc) a c < logb a, pak T(n) = O(nlogb a). Je-li f(n) = (nlogb a), pak T(n) = O(nlogb a log n). Je-li f(n) = (nc) a c > logb a, pak T(n) = O(nc). Důkaz tohoto obecného tvrzení přesahuje rozsah našeho předmětu. Všimněte si, že nikde ve výše uvedených řešeních nevystupují počáteční podmínky, tj. hodnoty T(0), T(1), T(2), . . . ­ ty jsou "skryté" v naší O()-notaci. Dále v zápise pro zjednodušení zanedbáváme i necelé části argumentů, které mohou být zaokrouhlené. ' $' & $ %Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.8. Algoritmus merge-sort pro třídění čísel pracuje zhruba násle- dovně: Danou posloupnost n čísel rozdělí na dvě (skoro) poloviny. Každou polovinu setřídí zvlášť za použití rekurentní aplikace merge-sort. Tyto dvě už setříděné poloviny "slije" (anglicky merge) do jedné setříděné výsledné posloupnosti. Jaký je celkový počet jeho kroků? ' $' & $ %Petr Hliněný, FI MU Brno 12 IB000 "Úv. Inf.": Délka výpočtu algoritmu Příklad 12.8. Algoritmus merge-sort pro třídění čísel pracuje zhruba násle- dovně: Danou posloupnost n čísel rozdělí na dvě (skoro) poloviny. Každou polovinu setřídí zvlášť za použití rekurentní aplikace merge-sort. Tyto dvě už setříděné poloviny "slije" (anglicky merge) do jedné setříděné výsledné posloupnosti. Jaký je celkový počet jeho kroků? Nechť na vstupu je n čísel. Při rozdělení na poloviny nám vzniknou podproblémy o velikostech n/2 a n/2 (pozor na necelé poloviny). Pokud počet kroků výpočtu označíme T(n), pak rekurzivní volání trvají celkem T( n/2 ) + T( n/2 ) . Dále potřebujeme c n kroků (kde c je vhodná konstanta) na slití obou částí do výsledného setříděného pole. Celkem tedy vyjde T(n) = T( n/2 ) + T( n/2 ) + cn T( n/2 ) + T( n/2 ) + cn a to už je tvar řešený v Lematu 12.6 pro a1 = a2 = 1 2 . Výsledek tedy je T(n) = O(n log n). 2