Petr Hliněný, FI MU Brno 1 FI: IB000: 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 FI: IB000: 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 9.1. Definice: Délkou výpočtu výrazu F nad deklarací rozumíme nejmenší přirozené k takové, že pro něj existuje m Num pro něž F k m. 2 (Když takové m neexistuje, klademe k = .) Jaká je délka výpočtu následujících výrazů? 3 + 4 - 5 6 ; 2tři kroky 3 + 4 - 5 6 3 + 4 - 30 3 + 0 3. 3 + (5 - 4) (6 ÷ 2) ; 2tentokrát čtyři kroky 3 + (5 - 4) (6 ÷ 2) 3 + 1 (6 ÷ 2) 3 + 1 3 3 + 3 6. 2009 ; 2žádný krok, tj. k = 0. Petr Hliněný, FI MU Brno 3 FI: IB000: 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 fi . Věta. Pro každé n je délka výpočtu výrazu f(n) rovna 4n + 2.2 Důkaz povedeme indukcí podle n: * Báze n = 0. Platí f(0) if 0 then 0 f(0 - 1) else 1 fi 1, což jsou přesně 2 kroky, tj. 4 0 + 2.2 * Indukční krok. Nechť n + 1 k. Pak f(k) if k then k f(k - 1) else 1 fi k f(k - 1) k f(w) , kde w k - 1 = n. 2To 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 2 Petr Hliněný, FI MU Brno 4 FI: IB000: 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í. 2 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 FI: IB000: 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 : je daná funkce. Pro funkci f : píšeme f O(g) pokud existují konstanty A, B > 0 takové, že 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 FI: IB000: 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". 2 Znaˇcen´i: 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 FI: IB000: 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. foreach i 1,2,3,...,n-1,n do foreach j 1,2,3,...,i-1,i do vytiskni 'x'; done done 2 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 po 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 FI: IB000: 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 FI: IB000: 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 : 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 n T(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 FI: IB000: 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 : 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 FI: IB000: Délka výpočtu algoritmu V obecnosti je známo: Lema 12.7. Nechť a 1, b > 1 jsou konstanty, f : je funkce a pro funkci T : 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 FI: IB000: 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ů? 2 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 Petr Hliněný, FI MU Brno 13 FI: IB000: Délka výpočtu algoritmu Příklad 12.9. Předpokládejme na vstupu dvě ,,dlouhá 2m-místná čísla (pro jednoduchost v dekadickém zápise) A a B. Součin A B můžeme rychleji (než školním postupem) vypočítat takto: Čísla si ,,rozdělíme na poloviny , tj. na čtyři m-místná čísla taková, že A = A1 + 10mA2 a B = B1 + 10mB2. Rekurzivní aplikací téhož postupu vypočteme tři součiny C1 = A1 B1, C2 = A2 B2 a D = (A1 + A2) (B1 + B2). Dále už jen sečteme (ověřte si snadno sami) A B = C1 + 10m (D - C1 - C2) + 102m C2 . Jaký je celkový počet jeho kroků? Postupujeme obdobně předchozímu příkladu. Nechť T(n) je počet kroků výpočtu pro vstupní čísla A a B délky nejvýše n = 2m. Tři rekurzivní volání pro součiny se aplikují na čísla délek nejvýše m a m+1 (pro (A1+A2)(B1+B2)), takže trvají celkem T(n/2) + T(n/2) + T(n + 1). 2Pomocné výpočtu součtu a rozdílu snadno vykonáme v O(n) krocích a pomocné násobení mocninou 10 je pouhým posunutím číslic. Petr Hliněný, FI MU Brno 14 FI: IB000: Délka výpočtu algoritmu Celkem tedy T(n) = 2T(n/2) + T(n + 1) + O(n) 3T(n/2 + 1) + O(n) . Navíc člen ,,+1 lze v argumentu asymptoticky zanedbat, a proto podle Lematu 12.7 vypočítáme log2 3 1.585 > 1 a T(n) = O(nlog2 3) O(n1.585), což je výrazně rychlejší než školní postup v čase O(n2) pro velká n. 2