12
D´ elka v´ ypoˇ ctu algoritmu
Mimo samotn´e spr´avnosti v´ysledku vypoˇcten´eho zapsan´ym algoritmem je jeˇstˇe jedno nem´enˇe d˚ uleˇzit´e hledisko k posouzen´ı vhodnosti algoritmu k ˇreˇsen´ı zadan´e ´ulohy. Jedn´a se o ˇcas, kter´y algoritmus str´av´ı v´ypoˇctem. Asi netˇreba argumentovat, ˇze pˇrehnanˇe dlouh´a doba odezvy programu je kaˇzd´emu uˇzivateli nepˇr´ıjemn´a. A co tˇreba v real-time syst´emech, kde si zdrˇzen´ı prostˇe nem˚ uˇzeme dovolit! Oblig´atn´ı odpovˇed’ kupme si rychlejˇs´ı poˇc´ıtaˇc“ bohuˇzel nen´ı vˇzdy ˇreˇsen´ım, jak pˇri ” pokroˇcil´em studiu sloˇzitosti algoritm˚ u sami pozn´ate. Mnohem vˇetˇs´ı potenci´al zrychlen´ı se skr´yv´a v algoritmech samotn´ych a jejich efektivn´ım n´avrhu.
Struˇ cn´ y pˇrehled lekce * D´elka v´ypoˇctu algoritmu, definice na naˇsem deklarativn´ım jazyce. * Asymptotick´e urˇcen´ı d´elky v´ypoˇctu – asymptotick´e chov´an´ı funkc´ı. * Asymptotick´e odhady rekurentn´ıch vztah˚ u.
Petr Hlinˇ en´ y, FI MU Brno
1
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
12.1
O v´ yznamu d´ elky v´ ypoˇ ctu algoritmu
Uvaˇzme deklarativn´ı jazyk Definice 9.1. Definice: D´elkou v´ypoˇctu v´yrazu F nad deklarac´ı ∆ rozum´ıme nejmenˇs´ı pˇrirozen´e k takov´e, ˇze pro nˇej existuje m ∈ Num pro nˇeˇz F 7→ k m. 2 (Kdyˇz takov´e m neexistuje, klademe k = ∞.) Jak´a je d´elka v´ypoˇctu n´asleduj´ıc´ıch v´yraz˚ u? ∗ 3 + 4 − 5 ∗ 6 ; 2tˇri kroky 3 + 4 − 5 ∗ 6 7→ 3 + 4 − 30 7→ 3 + 0 7→ 3. ∗ 3 + (5 − 4) ∗ (6 ÷ 2) ; 2tentokr´at ˇctyˇri kroky 3 + (5 − 4) ∗ (6 ÷ 2) 7→ 3 + 1 ∗ (6 ÷ 2) 7→ 3 + 1 ∗ 3 7→ 3 + 3 7→ 6. ∗ 2010 ; 2ˇz´adn´y krok, tj. k = 0.
Petr Hlinˇ en´ y, FI MU Brno
2
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
Pˇr´ıklad 12.1. Pro uk´azku uvaˇzme deklaraci ∆ obsahuj´ıc´ı pouze rovnici f (x) = if x then x ∗ f (x − 1) else 1 fi . Vˇ eta. Pro kaˇzd´e n ∈
N je d´elka v´ypoˇctu v´yrazu f (n) rovna 4n + 2.2
D˚ ukaz povedeme indukc´ı podle n: • B´aze n = 0. Plat´ı f (0) 7→ if 0 then 0 ∗ f (0 − 1) else 1 fi 7→ 1, coˇz jsou pˇresnˇe 2 kroky, tj. 4 · 0 + 2.2 • Indukˇcn´ı krok. Necht’ n + 1 ≡ k. Pak
f (k) 7→ if k then k ∗ f (k − 1) else 1 fi 7→ k ∗ f (k − 1) 7→ k ∗ f (w) , kde w ≡ k − 1 = n. 2To jsou pˇresnˇe 3 kroky. Podle I.P. je d´elka v´ypoˇctu v´yrazu f (w) rovna 4n+2. Pot´e n´ asleduje jeˇstˇe jeden posledn´ı krok vyn´asoben´ı k. Celkem se provedlo 3 + 4n + 2 + 1 = 4(n + 1) + 2 = 4k + 2 krok˚ u. 2 2
Petr Hlinˇ en´ y, FI MU Brno
3
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
Poˇ c´ıtat pˇresnˇ e nebo radˇ eji ne? Jak´y m´a smysl urˇcen´ı pˇresn´eho poˇctu krok˚ u algoritmu pˇri dneˇsn´ıch CPU? Copak jsme dnes schopni jednoznaˇcnˇe ˇr´ıci, jak dlouho jedna instrukce CPU trv´a? Z druh strany, i kdyˇz v´ıme, ˇze algoritmus A tˇreba potˇrebuje 2n krok˚ u v´ypoˇctu u, je mezi nimi aˇz takov´y rozd´ıl? Staˇc´ı, a algoritmus B tˇreba potˇrebuje 3n krok˚ kdyˇz B spust´ıme na dvakr´ at rychlejˇs´ım poˇc´ıtaˇci a pomˇer se hned obr´at´ı. 2 Obˇe tyto prakticky motivovan´e u ´vahy n´ as povedou k pozn´ an´ı, ˇze aditivn´ı a multiplikativn´ı faktory funkce poˇctu krok˚ u algoritmu jsou vlastnˇe zanedbateln´e.
Petr Hlinˇ en´ y, FI MU Brno
4
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
12.2
Asymptotick´ e znaˇ cen´ı a odhady funkc´ı
Zaj´ım´a-li n´as jen rychlost r˚ ustu funkce f (n) v z´ avislosti na n, zamˇeˇrujeme se an´ı f pˇri velk´ych hodnot´ach n. pˇredevˇs´ım na tzv. asymptotick´e chov´ V popisu f n´as tedy nezaj´ımaj´ı ani “drobn´e ˇcleny”, ani konstanty, kter´ymi je f n´asobena a kter´e jen ovlivˇ nuj´ı ˇc´ıselnou hodnotu f (n), ale ne rychlost r˚ ustu. 2
Definice: Necht’ g :
R → R je dan´a funkce. Pro funkci f : R → R p´ıˇseme f ∈O g
pokud existuj´ı konstanty A, B > 0 takov´e, ˇze ∀n ∈
R+ : f (n) ≤ A · g(n) + B .
V praxi se obvykle (i kdyˇz matematicky m´enˇe pˇresnˇe) p´ıˇse m´ısto f ∈ O g v´yraz f (n) = O g(n) .
Znamen´a to, slovnˇe ˇreˇceno, ˇze funkce f neroste rychleji neˇz funkce g. (I kdyˇz pro mal´a n tˇreba m˚ uˇze b´yt f (n) mnohem vˇetˇs´ı neˇz g(n).) Petr Hlinˇ en´ y, FI MU Brno
5
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
Definice: P´ıˇseme f ∈ Ω g , neboli f (n) = Ω g(n) , pokud g ∈ O(f ). D´ ale p´ıˇseme f ∈ Θ g , neboli f (n) = Θ g(n) , pokud f ∈ O(g) a z´aroveˇ n f ∈ Ω(g), neboli g ∈ O(f ). V´yraz f (n) = Θ g(n) pak ˇcteme jako “funkce f roste stejnˇe rychle jako funkce g”. 2 Znaˇ cen´ı: O funkci f (n) ˇr´ık´ ame: ∗ f (n) = Θ(n) je line´ arn´ı funkce,
∗ f (n) = Θ(n2 ) je kvadratick´ a funkce,
∗ f (n) = Θ(log n) je logaritmick´ a funkce,
∗ f (n) = O(nc ) pro nˇejak´e c > 0 je polynomi´ aln´ı funkce,
∗ f (n) = Ω(cn ) pro nˇejak´e c > 1 je exponenci´ aln´ı funkce. Petr Hlinˇ en´ y, FI MU Brno
6
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
Pˇr´ıklad 12.2. Pˇr´ıklady r˚ ust˚ u r˚ uzn´ych funkc´ı. Funkce f (n) = Θ(n): pokud n vzroste na dvojn´asobek, tak hodnota f (n) takt´eˇz vzroste (zhruba) na dvojn´ asobek. 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´asobek, tak hodnota f (n) vzroste (zhruba) na ˇctyˇrn´ asobek. To plat´ı jak pro funkci f (n) = n2 , tak i pro 2 2 1000n + 1000n nebo n − 99999999n − 99999999, atd. Naopak pro funkci f (n) = Θ(2n): pokud n vzroste byt’ jen o 1, tak hodnota f (n) uˇz vzroste (zhruba) na dvojn´ asobek. To je obrovsk´y rozd´ıl exponenci´aln´ıch proti polynomi´aln´ım funkc´ım. Pokud v´am tˇreba funkce 999999n2 pˇripad´ a velk´ a, jak stoj´ı ve srovn´an´ı s 2n ? Zvolme tˇreba n = 1000, kdy 999999n2 = 999999000000 je jeˇstˇe rozumnˇe zapsateln´e ˇc´ıslo, ale 21000 ≃ 10300 byste uˇz na ˇr´ adek nenapsali. Pro n = 10000 je rozd´ıl jeˇstˇe mnohem v´yraznˇejˇs´ı! 2
Petr Hlinˇ en´ y, FI MU Brno
7
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
Pˇr´ıklad 12.3. (opakovan´y) Zjistˇete, kolik znak˚ u ’x’ v z´avislosti na celoˇc´ıseln´e hodnotˇe n vstupn´ıho parametru n vyp´ıˇse n´ asleduj´ıc´ı algoritmus. Algoritmus 12.4. foreach i ← 1,2,3,...,n-1,n do foreach j ← 1,2,3,...,i-1,i vytiskni ’x’; done done 2
do
Zat´ımco v Lekci 8 jsme trochu zdlouhavˇe indukc´ı dokazovali, ˇze v´ysledkem je 1 ı si mnohem snadnˇeji odvod´ıme, ˇze poˇcet ’x’ je Θ(n2 ), coˇz 2 n(n + 1) ’x’, nyn´ a odpovˇed’ ve vˇetˇsinˇe informatick´ych aplikac´ı. je dostaˇcuj´ıc´ı asymptotick´ D˚ ukaz: Shora hned odhadneme, ˇze kaˇzd´ a z n iterac´ı vnˇejˇs´ıho cyklu vytiskne po i ≤ n znak˚ u ’x’, takˇze celkem je nejv´yˇse n2 ’x’. Naopak zdola hned vid´ıme, ˇze posledn´ıch n/2 iterac´ı vnˇejˇs´ıho cyklu vytiskne i ≥ n/2 znak˚ u ’x’, takˇze celkem je alespoˇ n (n/2) · (n/2) = n2 /4 ’x’. Z toho podle definice hned vyjde asymptotick´y odhad Θ(n2 ). 2
Petr Hlinˇ en´ y, FI MU Brno
8
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
12.3
Rekurentn´ı odhady
V tomto odd´ıle si uvedeme kr´ atk´y pˇrehled nˇekter´ych rekurentn´ıch vzorc˚ u, se kter´ymi se m˚ uˇzete setkat pˇri ˇreˇsen´ı ˇcasov´e sloˇzitosti (pˇrev´aˇznˇe rekurzivn´ıch) algoritm˚ u. Lema 12.5. Necht’ a1 , . . . , ak , c > 0 jsou kladn´e konstanty takov´e, ˇze a1 + nuje nerovnost · · · + ak < 1, a funkce T : → splˇ
N N
T (n) ≤ T (⌈a1 n⌉) + T (⌈a2 n⌉) + · · · + T (⌈ak n⌉) + cn . Pak T (n) = O(n).
2
D˚ ukaz: Zvolme ε > 0 takov´e, ˇze a1 + · · · + ak < 1 − 2ε. Pak pro dostateˇcnˇe velk´a n plat´ı (i se zaokrouhlen´ım nahoru) ⌈a1 n⌉ + · · · + ⌈ak n⌉ ≤ (1 − ε)n, ˇreknˇeme pro vˇsechna n ≥ n0 . D´ ale zvolme dostateˇ cnˇe velk´e d > 0 tak, ˇze εd > c a z´aroveˇ n d > max n1 T (n) : n = 1, . . . , n0 . D´ ale uˇz snadno indukc´ı podle n dok´ aˇzeme T (n) ≤ dn pro vˇsechna n ≥ 1: • Pro n ≤ n0 je T (n) ≤ dn podle naˇs´ı volby d. Petr Hlinˇ en´ y, FI MU Brno
9
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
• Pˇredpokl´adejme, ˇze T (n) ≤ dn plat´ı pro vˇsechna n < n1 , kde n1 > n0 je libovoln´e. Nyn´ı dok´aˇzeme i pro n1 T (n1 ) ≤ T (⌈a1 n1 ⌉) + · · · + T (⌈ak n1 ⌉) + cn1 ≤ ≤ d · ⌈a1 n1 ⌉ + · · · + d · ⌈ak n1 ⌉ + cn1 ≤ ≤ d · (1 − ε)n1 + cn1 ≤ dn1 − (εd − c)n1 ≤ dn1 . 2 Lema 12.6. Necht’ k ≥ 2 a a1 , . . . , ak , c > 0 jsou kladn´e konstanty takov´e, ˇze a1 + · · · + ak = 1, a funkce T : → splˇ nuje nerovnost
N N
T (n) ≤ T (⌈a1 n⌉) + T (⌈a2 n⌉) + · · · + T (⌈ak n⌉) + cn . Pak T (n) = O(n · log n).
Petr Hlinˇ en´ y, FI MU Brno
10
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
V obecnosti je zn´amo: Lema 12.7. Necht’ a ≥ 1, b > 1 jsou konstanty, f : funkci T : → plat´ı rekurentn´ı vztah n T (n) ≤ a · T + f (n) . b
N N
N → N je funkce a pro
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˚ ukaz tohoto obecn´eho tvrzen´ı pˇresahuje rozsah naˇseho pˇredmˇetu. Vˇsimnˇete si, ˇze nikde ve v´yˇse uveden´ych ˇreˇsen´ıch nevystupuj´ı poˇc´ateˇcn´ı podm´ınky, tj. hodnoty T (0), T (1), T (2), . . . – ty jsou “skryt´e” v naˇs´ı O()-notaci. D´ ale v z´apise pro zjednoduˇsen´ı zanedb´ av´ ame i necel´e ˇc´asti argument˚ u, kter´e mohou b´yt zaokrouhlen´e.
Petr Hlinˇ en´ y, FI MU Brno
11
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
Pˇr´ıklad 12.8. Algoritmus merge-sort pro tˇr´ıdˇen´ı ˇc´ısel pracuje zhruba n´ asledovnˇe: ∗ Danou posloupnost n ˇc´ısel rozdˇel´ı na dvˇe (skoro) poloviny.
∗ Kaˇzdou polovinu setˇr´ıd´ı zvl´ aˇst’ za pouˇzit´ı rekurentn´ı aplikace merge-sort.
∗ Tyto dvˇe uˇz setˇr´ıdˇen´e poloviny “slije” (anglicky merge) do jedn´e setˇr´ıdˇen´e v´ysledn´e posloupnosti. Jak´y je celkov´y poˇcet jeho krok˚ u?
2
Necht’ na vstupu je n ˇc´ısel. Pˇri rozdˇelen´ı na poloviny n´am vzniknou podprobl´emy o velikostech ⌈n/2⌉ a ⌊n/2⌋ (pozor na necel´e poloviny). Pokud poˇcet krok˚ u an´ı trvaj´ı celkem v´ypoˇctu oznaˇc´ıme T (n), pak rekurzivn´ı vol´ T (⌈n/2⌉) + T (⌊n/2⌋) . D´ ale potˇrebujeme c · n krok˚ u (kde c je vhodn´ a konstanta) na slit´ı obou ˇc´ast´ı do v´ysledn´eho setˇr´ıdˇen´eho pole. Celkem tedy vyjde T (n) = T (⌈n/2⌉) + T (⌊n/2⌋) + cn ≤ T (⌈n/2⌉) + T (⌈n/2⌉) + cn a to uˇz je tvar ˇreˇsen´y v Lematu 12.6 pro a1 = a2 = T (n) = O(n · log n). Petr Hlinˇ en´ y, FI MU Brno
12
1 2.
V´ysledek tedy je 2
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
Pˇr´ıklad 12.9. Pˇredpokl´ adejme na vstupu dvˇe dlouh´a“ 2m-m´ıstn´a ˇc´ısla (pro ” jednoduchost v dekadick´em z´ apise) A a B. Souˇcin A · B m˚ uˇzeme rychleji (neˇz ˇskoln´ım postupem) vypoˇc´ıtat takto: ˇısla si rozdˇel´ıme na poloviny“, tj. na ˇctyˇri m-m´ıstn´a ˇc´ısla takov´a, ˇze ∗ C´ ” A = A1 + 10m A2 a B = B1 + 10m B2 . ∗ Rekurzivn´ı aplikac´ı t´ehoˇz postupu vypoˇcteme tˇri souˇciny C1 = A1 · B1 , C2 = A2 · B2 a D = (A1 + A2 ) · (B1 + B2 ). ∗ D´ale uˇz jen seˇcteme (ovˇeˇrte si snadno sami)
A · B = C1 + 10m (D − C1 − C2 ) + 102m C2 . Jak´y je celkov´y poˇcet jeho krok˚ u? Postupujeme obdobnˇe pˇredchoz´ımu pˇr´ıkladu. Necht’ T (n) je poˇcet krok˚ u v´ypoˇctu pro vstupn´ı ˇc´ısla A a B d´elky nejv´yˇse n = 2m. Tˇri rekurzivn´ı vol´an´ı pro souˇciny se aplikuj´ı na ˇc´ısla d´elek nejv´yˇse m a m + 1 (pro (A1 + A2 ) · (B1 + B2 )), takˇze trvaj´ı celkem T (⌈n/2⌉) + T (⌈n/2⌉) + T (⌈n/2⌉ + 1). 2Pomocn´e v´ypoˇctu souˇctu a rozd´ılu snadno vykon´ ame v O(n) kroc´ıch a pomocn´e n´asoben´ı mocninou 10 je pouh´ym posunut´ım ˇc´ıslic. Petr Hlinˇ en´ y, FI MU Brno
13
FI: IB000: D´ elka v´ ypoˇ ctu 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ˇc´ıt´ame log2 3 ≃ 1.585 > 1 a T (n) = O(nlog2 3 ) ≃ O(n1.585 ), 2 coˇz je v´yraznˇe rychlejˇs´ı neˇz ˇskoln´ı postup v ˇcase O(n2 ) pro velk´a n.
Petr Hlinˇ en´ y, FI MU Brno
14
FI: IB000: D´ elka v´ ypoˇ ctu algoritmu
