IB108
Sada 1, Pˇ r´ıklad 1
Vypracovali:
Tom´aˇs Krajˇca (255676), Martin Milata (256615)
log 3 3 Sloˇzitost tˇr´ıd´ıc´ıho algoritmu 1/3-Sort je v O n 2 ∈ O (n2.71 ). Necht’ n = j − i (velikost pole, kter´e je vstupn´ım parametrem funkce 1/3-Sort). Lehce uˇzeme spoˇc´ıt´ame, ˇze velikost pole pˇred´avan´a rekurzivnˇe volan´ ym 1/3-Sort je ≤ 23 n. Z toho m˚ odvodit rekurentn´ı rovnici: 2 n + c, kde c ∈ N T (n) = 3T 3 T (1) = c0 , kde c0 ∈ N log 3 3 Dle Master Theorem je tedy T (n) ∈ O n 2 , (a = 3, b = 23 , d = 0). Algoritmus korektnˇe utˇr´ıd´ı danou posloupnost. Algoritmus konverguje - zˇrejm´e, pro i + 1 < j bude k ≥ 1, tedy rekurzivnˇe volan´e funkce budou m´ıt jako parametr alepoˇ n o 1 menˇs´ı pole, neˇz mˇela p˚ uvodn´ı funkce. Pro i + 1 ≥ j konˇc´ı rekurzivn´ı zanoˇrov´an´ı. Algoritmus je parci´alnˇe korektn´ı. Invariant: V kaˇzd´em exempl´aˇri funkce 1/3−Sort je moˇzn´e vstupn´ı pole rozdˇelit na n´asleduj´ıc´ı 3 ˇc´asti: A[i] . . . A[i + k] . . . A[j − k] . . . A[j], kde a) prostˇredn´ı ˇc´ast je alespoˇ n tak velk´a jako posledn´ı ˇc´ast a z´aroveˇ n b) prostˇredn´ı ˇc´ast je nepr´azdn´a a z´aroveˇ n c) prostˇredn´ı ˇc´ast je alespoˇ n tak velk´a jako prvn´ı ˇc´ast. a) (j − k) − (i + k) = j − k − k − i
≥ k − 1 = j − (j − k + 1) ⇐⇒ j−k−k−k−i+1 ≥ 0 3j − j + i − 1 − 3i + 3 −k−k ≥ 0 3 2j − 2i + 2 j−i+1 j−i+1 − − ≥ 0 3 3 3 b) pˇredpokl´ad´ame, ˇze j ≥ i + 2 (ˇr´adek 3 algoritmu). (i + 2) − i + 1 (i + 2) − i + 1 (j − k) − (i + k) = j − k − k − i ≥ (i + 2) − − −i=0 3 3 c) (j − k) − (i + k) ≥ k − 1 = (i + k − 1) − i Pokraˇcov´an´ı na dalˇs´ım listu.
1
IB108
Sada 1, Pˇ r´ıklad 1
Vypracovali:
Tom´aˇs Krajˇca (255676), Martin Milata (256615)
Nyn´ı indukc´ı k d´elce vstupn´ıho pole uk´aˇzeme parci´aln´ı korektnost algoritmu. Pro pole d´elky 2 (trivi´alnˇe pro d´elku 1): z ˇr´adk˚ u 1 − 4 algoritmu je zˇrejm´e, ˇze b´aze indukce plat´ı (ˇz´adn´e rekurzivn´ı zanoˇrov´an´ı). Pˇredpokl´adejme tedy, ˇze dan´ y algoritmus korektnˇe utˇr´ıd´ı pole d´elky n−1. Pak volejme funkci 1/3 − Sort(A, i, j) : j − i = n. Dle indukˇcn´ıho pˇredpokladu n´am vol´an´ı funkce 1/3 − Sort na ˇr´adku 6 utˇr´ıd´ı ˇc´ast pole A[l] . . . A[j − k]. Pot´e vol´an´ı na ˇr´adku 7 n´am utˇr´ıd´ı ˇc´ast pole A[i + k] . . . A[j]. Pˇriˇcemˇz bude platit: A[i], A[i + 1], . . . , A[j − k] ≤ A[j − k + 1] ≤ A[j − k + 2] · · · ≤ A[j] Plyne z invariantu z velikosti jednotliv´ ych ˇc´ast´ı pole. Dalˇs´ı rekurzivn´ı vol´an´ı funkce 1/3−Sort na ˇr´adku 8 n´am setˇr´ıd´ı zb´ yvaj´ıc´ı ˇc´ast pole A[i] . . . A[j − k].
2
IB108
Sada 1, Pˇ r´ıklad 2
Vypracovali:
Tom´aˇs Krajˇca (255676), Martin Milata (256615)
Necht’ pˇriˇrazen´ı trv´a 1 ˇcasovou jednotku, pak pˇresn´a ˇcasov´a sloˇzitost algoritmu 5 3 1 n + 38 n2 + 12 n + 18 n4 + 1 ∈ O(n4 ). je 12 1 5 3 Funkce UNKNOWN(n) vypoˇc´ıt´a hodnotu 12 n + 38 n2 + 12 n + 18 n4 . Cyklus na ˇr´adku 4 probˇehne vˇzdy i kr´at ((i + j) − j = i). Protoˇze k ≥ j, cyklus na ˇr´adku 5 probˇehne i kr´at, i − 1 kr´at . . . 1 kr´at (analyzujeme pouze cykly na ˇr´adc´ıch 4, 5). Tedy tato dvojice cykl˚ u probˇehne 2i · (i + 1). Cyklus na ˇr´adku 3 probˇehne i kr´at, tedy dohromady s cykly na ˇr´adc´ıch 4, 5 to bude T 0 (i) = i · 2i · (i + 1). Nyn´ı uˇz snadno nahl´edneme, ˇze plat´ı rekurentn´ı vztahy (analyzujeme vˇsechny cykly): T (1)
=
1
n = T (n − 1) + T 0 (n) = T (n − 1) + · (n + 1) · n 2 ⇐⇒ 1 1 1 1 n+1 2−5 n+1 +3 n+1 n+1 T (n) = (n + 1) 2 3 3 4 1 3 5 1 T (n) = n + n2 + n3 + n4 12 8 12 8
T (n)
3
IB108 Vypracovali:
Sada 1, Pˇ r´ıklad 3 Tom´aˇs Krajˇca (255676), Martin Milata (256615)
Algoritmus: Require: P A[l..r], A[ ] ∈ Z j Ensure: k=i A[k] is maximum 1: max ← max suf ← 0 2: i ← j ← i suf ← j suf ← 0 3: for k ← l to r do 4: if 0 > max suf + A[k] then 5: max suf ← 0 6: i suf ← k + 1 7: else 8: max suf ← max suf + A[k] 9: j suf ← k 10: end if 11: if max < max suf then 12: max ← max suf 13: i ← i suf 14: j ← j suf 15: end if 16: end for 17: if max ≤ 0 then 18: max = A[l] 19: i←j←l 20: for k ← l + 1 to r do 21: if A[k] > max then 22: max ← A[k] 23: i←j←k 24: end if 25: end for 26: end if 27: return (i, j) Anal´ yza sloˇzitosti: Necht’ n = r − l je velikost pole A[ ]. Pak sloˇzitost algoritmu je zˇrejmˇe Θ(n) ∈ O (n · log n). M´ame 2 oddˇelen´e for cykly s n iteracemi. Pokraˇcov´an´ı na dalˇs´ım listu.
4
IB108 Vypracovali:
Sada 1, Pˇ r´ıklad 3 Tom´aˇs Krajˇca (255676), Martin Milata (256615)
Konvergence trivi´aln´ı - pouze 2 koneˇcn´e for cykly. Korektnost: Dok´aˇzeme, ˇze max je suma podintervalu pole A[ ], kter´a je maxim´aln´ı. Argumentace, ˇze nejlevˇejˇs´ı prvek takov´eho podintervalu je i a nejpravˇejˇs´ı j by byla obdobn´a. Tento invariant plat´ı po celou dobu v´ ypoˇctu.
(a) ∃b.A[b] > 0 Pro for cyklus na ˇr´adku 3 bude platit invariant: max je suma podintervalu pole A[l..k], kter´a je maxim´aln´ı. Dalˇs´ı invariant pro tento for cyklus je: max suf je suma podintervalu pole A[l..k], kter´a je maxim´aln´ı a z´aroveˇ n nejpravˇejˇs´ı prvek podintervalu je A[k]. Pokud by mˇela b´ yt promˇenn´a max nebo max suf z´aporn´a, pokl´ad´ame je rovny 0. To m˚ uˇzeme, protoˇze v´ıme, ˇze v poli existuje prvek vˇetˇs´ı neˇz 0. Po opuˇstˇen´ı tohoto for cyklu bude tedy v max suma podintervalu pole A[l..r], kter´a je maxim´aln´ı. Pˇredpokl´ad´ame, ˇze pole obsahuje nˇejak´ y prvek vˇetˇs´ı neˇz 0, if podm´ınka na ˇr´adku 17 se tedy vyhodnot´ı na f alse. (b) ∀b.A[b] ≤ 0 Zu ´vodn´ıho pˇredpokladu hned vid´ıme, ˇze podinterval s maxim´aln´ı sumou bude obsahovat 1 prvek (A[b] + A[c] ≤ A[b]). Necht’ tedy probˇehne u ´vodn´ıch 16 ˇr´adk˚ u, je zˇrejm´e, ˇze max ≤ 0, provedou se tedy ˇr´adky 18..26. To je ovˇsem aplikace standardn´ıho algoritmu pro nalezen´ı nejvˇetˇs´ıho prvku pole A[l..r]. Invariant pro for cyklus na ˇr´adku 20: max je maxim´aln´ı poloˇzka pole A[l..k]. Tento nejvˇetˇs´ı prvek pole bude jedin´ y prvek maxim´aln´ıho podintervalu pole A[l..r].
5
IB108
Sada 1, Pˇ r´ıklad 4
Vypracovali:
Tom´aˇs Krajˇca (255676), Martin Milata (256615)
Pro navrˇzen´ı datov´e struktury vyuˇzijeme n´asleduj´ıc´ı fakt. Mˇejme posloupnost ˇc´ısel (na obr´azku 1–32) a nad n´ı postaven´ y bin´arn´ı strom. D´ale pak mˇejme nˇejak´ y interval leˇz´ıc´ı v t´eto posloupnosti (na obr´azku 19–27). Na obr´azku jsou pro n´azornost vyznaˇceny obˇe cesty z koˇrene do krajn´ıch bod˚ u tohoto intervalu. Vlastnost, kter´a je pro n´as podstatn´a je, ˇze kaˇzd´a cesta z koˇrene do nˇej´ak´eho bodu intervalu vypad´a n´asledovnˇe: projde uzlem, kde se cesty do krajn´ıch interval˚ u rozdvojuj´ı (v hraniˇcn´ıch pˇr´ıpadech m˚ uˇze b´ yt tento uzel koˇren nebo list) a pak pokraˇcuje bud’ po cestˇe vedouc´ı do lev´eho krajn´ıho bodu a z n´ı odboˇc´ı doprava, nebo pokraˇcuj´ı po cestˇe do prav´eho krajn´ıho bodu a z n´ı odboˇc´ı doleva, pˇr´ıpadnˇe dojdou po jedn´e z tˇechto cest aˇz do krajn´ıho bodu.
1
2
3
4
5
6
7
8
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32
Jinak ˇreˇceno, projdou pr´avˇe jednou uzlem, kter´ y je prav´ ym (resp. lev´ ym) synem nˇej´ak´eho uzlu leˇz´ıc´ıho na cestˇe do lev´eho (resp. prav´eho) krajn´ıho bodu, kter´ y s´am na t´eto cestˇe neleˇz´ı (pokud nen´ı c´ılov´ y bod z´aroveˇ n bodem krajn´ım). Tyto uzly jsou na obr´azku vyznaˇceny teˇckou. Jako datovou strukturu tedy pouˇzijeme bin´arn´ı strom, do jehoˇz uzl˚ u si budeme ukl´adat pˇrirozen´a ˇc´ısla. Pro kaˇzd´ y zadan´ y interval najdeme v´ yˇse popsan´e uzly a pˇriˇcteme do nich ˇc´ıslo pˇriˇrazen´e dan´emu intervalu. T´ım dos´ahneme toho, ˇze na kaˇzd´e cestˇe z koˇrene do listu bude leˇzet takov´ y souˇcet ˇc´ısel, kter´ y odpov´ıd´a souˇctu ˇc´ısel pˇriˇrazen´ ych k interval˚ um, v nichˇz leˇz´ı ˇc´ıslo v listu. Pro nalezen´ı uzl˚ u, do kter´ ych budeme ukl´adat hodnoty n´am staˇc´ı proj´ıt obˇe cesty z koˇrene do krajn´ıch bod˚ u intervalu. Pˇri tom projdeme nejv´ yˇse tolik uzl˚ u, kolik je dvojn´asobek v´ yˇsky stromu. Pouˇzijeme-li vyv´aˇzen´ y bin´arn´ı strom, bude n´am to trvat logaritmick´ y ˇcas vzhledem k poˇctu list˚ u a tedy vzhledem k velikosti nosn´eho intervalu. Pro nalezen´ı souˇctu n´aleˇz´ıc´ıho nˇej´ak´emu ˇc´ıslu staˇc´ı proj´ıt uzly od koˇrene k dan´emu listu, coˇz bude tak´e trvat logaritmick´ y ˇcas. Protoˇze ve stromu uchov´av´ame souˇcty hodnot a protoˇze parametry druh´e operace jsou pouze krajn´ı body intervalu, mus´ıme si jeˇstˇe nˇekde uchov´avat jednotliv´a ˇc´ısla pˇriˇrazen´a ke kaˇzd´emu intervalu. Pro tento u ´ˇcel pouˇzijeme dvourozmˇern´e pole velikosti n × n (kde n m´a v´ yznam jako v zad´an´ı). 6
IB108 Vypracovali:
Sada 1, Pˇ r´ıklad 4 Tom´aˇs Krajˇca (255676), Martin Milata (256615)
Algoritmus pro inicializaci datov´e struktury vytvoˇr´ı vyv´aˇzen´ y bin´arn´ı strom. Hodnotu uzlu, nazvanou val, inicializuje na nulu. Pro zjednoduˇsen´ı si do uzl˚ u pˇrid´ame jeˇstˇe poloˇzku i, kter´a bude ud´avat hodnotu nejpravˇejˇs´ıho potomka lev´eho podstromu (v pˇr´ıpadˇe vnitˇrn´ıho uzlu), v pˇr´ıpadˇe listu jeho hodnotu. Algoritmus d´ale vytvoˇr´ı pole velikosti n × n, jehoˇz prvky inicializuje na nulu. Stav, kdy je k intervalu pˇriˇrazena nula a stav, kdy interval nen´ı ve struktuˇre obsaˇzen jsou z hlediska obou operac´ı nerozliˇsiteln´e. Init(n) 1: Tree ← InitTree(n, 0) 2: Arr ← alokuj pole velikosti n × n a vynuluj jeho prvky InitTree(size, offset) 1: leftsize ← bsize/2c 2: newnode ← alokuj nov´ y uzel 3: newnode.val ← 0 4: newnode.i ← leftsize + offset 5: if size = 1 then 6: newnode.left ← NIL 7: newnode.right ← NIL 8: newnode.i ← newnode.i + 1 9: else 10: newnode.left ← InitTree(leftsize,offset) 11: newnode.right ← InitTree(size − leftsize,offset + leftsize) 12: end if 13: return newnode Algoritmus pro nalezen´ı souˇctu ˇc´ısel pˇriˇrazen´ ych interval˚ um do kter´ ych patˇr´ı dan´e ˇc´ıslo k pouze sˇc´ıt´a hodnoty na cestˇe k listu s hodnotou k. Get(tree, k) 1: if tree = NIL then 2: return 0 3: else if k ≤ tree.i then 4: return Get(tree.left,k) + tree.val 5: else 6: return Get(tree.right,k) + tree.val 7: end if
7
IB108 Vypracovali:
Sada 1, Pˇ r´ıklad 4 Tom´aˇs Krajˇca (255676), Martin Milata (256615)
Algoritmus pro zmˇenu ˇc´ısla nejprve pˇriˇcte rozd´ıl nov´e a star´e hodnoty do uzl˚ u s vlastnost´ı uvedenou na zaˇc´atku a pot´e novou hodnotu zap´ıˇse do pole. Cesty k hraniˇcn´ım uzl˚ um se neproch´az´ı explicitnˇe dvakr´at, m´ısto toho se zjiˇst’uje vztah intervalu kter´ y mˇen´ıme a interval˚ u, kter´e jsou reprezentov´any obˇema podstromy a podle toho se bud’ algoritmus rekurzivnˇe zavol´a na dan´ y podstrom, nebo je do koˇrene podstromu pˇriˇcten rozd´ıl hodnot, nebo se neprovede nic. Pro lev´ y i prav´ y podstrom se tedy zjiˇst’uje, zda: • Interval reprezentovan´ y dan´ ym podstromem je cel´ y obsaˇzen v mˇenˇen´em intervalu. Pokud ano, je v jeho koˇreni obsaˇzena hodnota tohoto intervalu a pˇriˇcteme do nˇej tedy rozd´ıl nov´e a star´e hodnoty (podm´ınky na ˇr´adc´ıch 5 a 10). • Interval reprezentovan´ y dan´ ym podstromem je ˇc´asteˇcnˇe obsaˇzen v mˇenˇen´em intervalu. Pokud ano, leˇz´ı v nˇem hraniˇcn´ı bod intervalu, ke kter´emu se rekurzivn´ım vol´an´ım pˇribl´ıˇz´ıme (podm´ınky na ˇr´adc´ıch 7 a 12). Konjunkce podm´ınek na ˇr´adc´ıch 7 a 12, tedy situace, kdy lev´ y krajn´ı bod leˇz´ı v lev´em podstromˇe a prav´ y v prav´em, a kdy dojde ke dvˇema rekurzivn´ım vol´an´ım, m˚ uˇze zˇrejmˇe nastat pouze jednou. Update(int begin, int end, newvalue) 1: Update’(Tree,0,n,int begin,int end,newvalue − Arr[int begin][int end]) 2: Arr[int begin][int end] ← newvalue Update’(node, begin, end, int begin, int end, updval) 1: left begin ← begin 2: left end ← node.i 3: right begin ← left end+1 4: right end ← end 5: if left begin ≥ int begin ∧ left end ≤ int end then 6: node.left.val ← node.left.val + updval 7: else if int begin ≤ left end then 8: Update’(node.left, left begin, left end, int begin, int end, updval) 9: end if 10: if right begin ≥ int begin ∧ right end ≤ int end then 11: node.right.val ← node.right.val + updval 12: else if right begin ≤ int end then 13: Update’(node.right, right begin, right end, int begin, int end, updval) 14: end if
8
IB108 Vypracovali:
Sada 1, Pˇ r´ıklad 5 Tom´aˇs Krajˇca (255676), Martin Milata (256615)
Rozdˇelme kredity n´asledovnˇe (cena je vyj´adˇrena jako poˇcet pˇr´ıstup˚ u do pole): Operace Kredity Cena ˇidej Pr 1 1 ˇti Sec 4 3 ˇ Odstran-Maximum 0 cena shora ohraniˇcena hodnotou odstraˇ novan´eho prvku ˇti pˇrid´ame na u Pˇri kaˇzd´em pouˇzit´ı operace Sec ´ˇcet jeden kredit. Z´ısk´av´ame tak invariant, ˇze kaˇzd´e ˇc´ıslo n v multimnoˇzinˇe m´a na u ´ˇctu n − 1 kredit˚ u. Jin´ ymi slovy, kaˇzd´emu indexu pole i (s hodnotou Arr[i]) je pˇriˇrazeno Arr[i] · (i − 1) kredit˚ u. D˚ ukaz indukc´ı podle indexu i: B´ aze (i = 1) Nula kredit˚ u – trivi´alnˇe plat´ı. Indukˇ cn´ı krok Pˇredpokl´adejme, ˇze pro i = 1 . . . n tvrzen´ı plat´ı. Pak kaˇzd´e ˇc´ıslo n + 1 v multimnoˇzinˇe muselo vzniknout souˇctem dvou ˇc´ısel 1 ≤ a, b ≤ n, takˇze bude m´ıt ˇti. Tedy (a − 1) + pˇriˇrazen souˇcet jejich kredit˚ u a nav´ıc jeden kredit za operaci Sec (b − 1) + 1 = a + b − 1 = (n + 1) − 1 = n kredit˚ u. ˇ-Maximum je v nejhorˇs´ım pˇr´ıpadˇe rovna hodnotˇe odstraˇ Cena operace Odstran novan´eho maxima. Takov´ y pˇr´ıpad nastane, pokud je aktu´aln´ı maximum n jedin´ ym prvkem multimnoˇziny a po jeho odstranˇen´ı se mus´ı prohledat vˇsechny indexy menˇs´ı neˇz n, aby se urˇcilo nov´e maximum. Protoˇze m´a n na u ´ˇctu n − 1 kredit˚ u, m˚ uˇzeme zaplatit prohled´an´ı tˇechto n − 1 index˚ u, aniˇz bychom uvedli u ´ˇcet do z´aporn´eho stavu. V pˇr´ıpadˇe, ˇze jsou v multimnoˇzinˇe jeˇstˇe nˇejak´e prvky, m˚ uˇze b´ yt skuteˇcn´a cena operace menˇs´ı. To, ˇze n´am nˇejak´e kredity zbudou ovˇsem nen´ı podstatn´e. Posloupnost n operac´ı bude st´at nejv´ yˇse 4n kredit˚ u a je t´ım p´adem v O(n).
9
IB108 Vypracovali:
Sada 1, Pˇ r´ıklad 6 Tom´aˇs Krajˇca (255676), Martin Milata (256615)
1. Tvrzen´ı neplat´ı. Protipˇr´ıklad: Necht’ n ∈ N je vhodn´ y, velk´ y poˇcet operac´ı. Udˇel´ame n2 operac´ı INSERT(S,i), pot´e budeme uˇz jen stˇr´ıdat operace MIN-ALL(S) a INSERT(S,i+1) (v tomto poˇrad´ı). Takˇze udˇel´ame n2 + n4 operac´ı INSERT(S, ) a n4 operac´ı MINALL(S), kter´e odeberou jen prvek i+1 (cena bude n2 + 1). Tedy ˇcasov´a sloˇzitost tˇechto n operac´ı bude 3n · 1 + n4 · n2 + 1 ∈ Θ (n2 ). 4 2. Tvrzen´ı plat´ı. Analyzujeme technikou u ´ˇct˚ u: Kaˇzd´a operace INSERT(S, ) si pˇrinese 3 kredity. 1 kredit se pouˇzije na zaplacen´ı operace vloˇzen´ı, 1 kreditem se zaplat´ı (pokud to bude tˇreba) pˇr´ıstup na prvek pˇri operaci MIN-ONE(S). MIN-ONE(S) si nepˇrinese ˇz´adn´ y kredit. Invariantem tedy bude: na u ´ˇctu m´ame alespoˇ n 2 kr´at tolik kredit˚ u, kolik m´ame prvk˚ u v seznamu S. Protoˇze operace MIN-ONE(S) odstran´ı ze seznamu alespoˇ n 1 prvek (jinak by byla nezaj´ımav´a - st´ala konstantn´ı cenu), m˚ uˇzeme jeho 1 zbyl´ y kredit vloˇzit na u ´ˇcet jednoho neodstranˇen´eho prvku (ten na sv´em u ´ˇctu uˇz alespoˇ n 1 kredit m´ıt musel). Sloˇzitost n operac´ı tedy bude O(n).
10
IB108
Sada 1, Pˇ r´ıklad 9
Vypracovali:
Tom´aˇs Krajˇca (255676), Martin Milata (256615)
Horn´ı odhad Horn´ı odhad provedeme konstrukc´ı a anal´ yzou sloˇzitosti (ne nezbytnˇe optim´aln´ıho) algoritmu. Necht’ n znaˇc´ı poˇcet disk˚ u se kter´ ymi algoritmus pracuje (na poˇc´atku roven celkov´emu poˇctu disk˚ u), m pozici aktu´alnˇe nejvˇetˇs´ıho disku. if n = 1 then return else obrat’ m disk˚ u (takˇze nejvˇetˇs´ı disk bude nahoˇre) obrat’ n disk˚ u (nejvˇetˇs´ı disk bude dole) rekurzivnˇe zavolej tento algoritmus na n − 1 horn´ıch disk˚ u end if Algoritmus vyuˇz´ıv´a toho, ˇze (podobnˇe jako u z´asobn´ıku) m˚ uˇzeme pracovat jen s nˇekolika horn´ımi disky bez ohledu na to, co je pod nimi. Algoritmus je zˇrejmˇe konvergentn´ı (rekurze se sniˇzuj´ıc´ım se n) a korektnˇe uspoˇr´ad´a disky (indukc´ı – trivi´alnˇe pro jeden disk, pro n + 1 disk˚ u nejprve pˇresune nejvˇetˇs´ı disk dospoda a potom uspoˇr´ad´a zbyl´ ych n disk˚ u). Pˇritom provede 2n − 2 operac´ı ,,obrat’“. Doln´ı odhad Pro proveden´ı doln´ıho odhadu si staˇc´ı uvˇedomit tyto skuteˇcnosti: • C´ılov´e uspoˇr´ad´an´ı disk˚ u m´a tu vlastnost, ˇze kaˇzd´a dvojice vz´ajemnˇe soused´ıc´ıch disk˚ u se velikost´ı liˇs´ı o jedniˇcku. Tedy pro n disk˚ u existuje n−1 soused´ıc´ıch dvojic takov´ ych, ˇze se liˇs´ı pr´avˇe o jedna. • Proveden´ım jedn´e operace se poˇcet dvojic takov´ ych, kter´e se liˇs´ı o jedniˇcku zmˇen´ı nejv´ yˇse o jednu takovou dvojici (Obr´at´ıme-li m disk˚ u, zruˇs´ıme dvojici m, m + 1 a vznikne n´am dvojice 1, m + 1, ostatn´ım disk˚ um z˚ ustanou p˚ uvodn´ı soused´e). Z tˇechto pozorov´an´ı vypl´ yv´a, ˇze m´ame-li n disk˚ u v poˇrad´ı n n 1, n, 2, n − 1, 3, n − 2, . . . , , + 1 (pro sud´a n) 2 2 nebo 1, n, 2, n − 1, 3, n − 2, . . . ,
lnm
lnm
+ 1, (pro lich´a n), 2 2 tedy takov´em, kdy pouze jedna soused´ıc´ı dvojice je ve spr´avn´em poˇrad´ı, potˇrebujeme prov´est alespoˇ n n − 2 operac´ı otoˇcen´ı, abychom mohli dos´ahnout toho, ˇze budou disky seˇrazen´e podle velikosti. Dost´av´ame tedy A ∈ O(n) a z´aroveˇ n A ∈ Ω(n), coˇz mimo jin´e znamen´a, ˇze algoritmus z horn´ıho odhadu je asymptoticky optim´aln´ı.
11
