Datové struktury - haldy a třídicí algoritmy

Datové struktury - haldy a tˇr´ıdic´ı algoritmy ´ I. Uvod V praxi se ˇcasto setkáváme s následuj´ıc´ım problémem, kter´ y vznik´ a na uspoˇr´ adaném uni´ verzu, jehoˇz uspoˇrádán´ı se vˇsak v pr˚ ubˇehu ˇcasu mˇen´ı. Uloha se liˇs´ı od slovn´ıkového problému v tom, ˇze se nevyˇzaduje efektivn´ı operace MEMBER. Dokonce se pˇredpokl´ adá, ˇze operace dostane spolu s argumentem informaci o uloˇzen´ı zpracov´ avaného prvku. Hlavn´ım poˇzadavkem je rychlost provededn´ı ostatn´ıch operac´ı a malé pamˇeˇtové n´ aroky. Pˇritom v praxi obvykle nestaˇc´ı znát jen asymptotickou sloˇzitost, d˚ uleˇzitou roli hraje skuteˇcná rychlost, kterou vˇsak neum´ıme obecnˇe spoˇc´ıtat, protoˇze je z´ avisl´ a na pouˇzitém systému a hardwaru. Pˇresto je pˇri pouˇzit´ı následuj´ıc´ıch struktur dobré m´ıt realistickou pˇredstavu o skuteˇcn´ ych rychlostech operac´ı a podle toho si vybrat vhodnou strukturu. Upravený Zadán´ı problému: Nechˇt U je univerzum. Je d´ ana mnoˇzina S ⊆ U a funkce f : S − → R, slovníkový kde R jsou re´ alná ˇc´ısla (tato funkce realizuje uspoˇr´ ad´ an´ı na univerzu U – pro u, v ∈ U plat´ı problém:

Operace:

u ≤ v, právˇe kdyˇz f (u) ≤ f (v); zmˇena uspoˇr´ ad´ an´ı se pak realizuje zmˇenou funkce f ). Máme navrhnout reprezentaci S a f , která umoˇzn ˇuje operace: INSERT(s, a) – pˇridá k mnoˇzinˇe S prvek s tak, ˇze f (s) = a, MIN – nalezne prvek s ∈ S s nejmenˇs´ı hodnotou f (s), DELETEMIN – odstran´ı prvek s ∈ S s nejmenˇs´ı hodnotou f (s), DELETE(s) – odstran´ı prvek s ∈ S z mnoˇziny S, DECREASE(s, a) – zmenˇs´ı hodnotu f (s) o a (tj. f (s) := f (s) − a), INCREASE(s, a) – zvˇetˇs´ı hodnotu f (s) o a (tj. f (s) := f (s) + a). Pˇri operaci INSERT(s, a) se pˇredpokl´ ad´ a, ˇze s ∈ / S, a tento pˇredpoklad operace INSERT neovˇeˇruje. Pˇri operac´ıch DELETE(s), DECREASE(s, a) a INCREASE(s, a) se pˇredpokládá, ˇze s ∈ S, a operace nav´ıc dost´ av´ a informaci, jak naj´ıt prvek s v reprezentaci S a f . Haldy jsou typ struktury, která se pouˇz´ıv´ a pro ˇreˇsen´ı tohoto problému.

Halda je stromová struktura, kde vrcholy reprezentuj´ı prvky z S a splˇ nuj´ı lok´ aln´ı podm´ınku na f . Obvykle se pouˇz´ıvá následuj´ıc´ı podm´ınka nebo jej´ı du´ aln´ı verze: (usp) Pro kaˇzd´ y vrchol v plat´ı: kdyˇz v reprezentuje prvek s ∈ S a otec(v) reprezentuje t ∈ S, pak f (t) ≤ f (s).

Další operace:

Probereme nˇekolik verz´ı hald a budeme pˇredpokl´ adat, ˇze vˇzdy splˇ nuj´ı tuto podm´ınku a ˇze poˇzadavek na proveden´ı operac´ı DELETE(s), DECREASE(s, a) a INCREASE(s, a) také zadává ukazatel na vrchol reprezentuj´ıc´ı s ∈ S. Nav´ıc budeme uvaˇzovat operace : MAKEHEAP(S, f ) – operace vytvoˇr´ı haldu reprezentuj´ıc´ı mnoˇzinu S a funkci f , MERGE(H1 , H2 ) – pˇredpokládá, ˇze halda Hi reprezentuje mnoˇzinu Si a funkci fi pro i = 1, 2 a S1 ∩ S2 = ∅. Operace vytvoˇr´ı haldu H reprezentuj´ıc´ı S1 ∪ S2 a f1 ∪ f2 , pˇriˇcemˇz neovˇeˇruje disjunktnost S1 a S2 .

1

2

II. Regul´ arn´ı haldy Prvn´ı pouˇzité haldy byly binárn´ı neboli 2-regul´ arn´ı haldy. Tyto haldy jsou velmi obl´ıbené pro svou jednoduchost a názornost a pro velmi efektivn´ı implementaci. Pˇredpokládejme, ˇze d > 1 je pˇrirozené ˇc´ıslo. d-regul´ arn´ı strom je koˇrenov´ y strom (T, r), pro kter´ y existuje poˇrad´ı syn˚ u jednotliv´ ych vnitˇrn´ıch vrchol˚ u takové, ˇze oˇc´ıslován´ı vrchol˚ u prohledáván´ım do ˇs´ıˇrky (koˇren r je ˇc´ıslov´ an 1) splˇ nuje n´ asleduj´ıc´ı vlastnosti (1) kaˇzd´ y vrchol má nejv´ yˇse d syn˚ u, (2) kdyˇz vrchol nen´ı list, tak vˇsechny vrcholy s menˇs´ım ˇc´ıslem maj´ı pr´ avˇe d syn˚ u, (3) kdyˇz vrchol má ménˇe neˇz d syn˚ u, pak vˇsechny vrcholy s vˇetˇs´ımi ˇc´ısly jsou listy. u

k v

Toto oˇc´ıslován´ı se naz´ yvá pˇrirozené oˇc´ıslov´ an´ı d-regul´ arn´ıho stromu. Tvrzen´ı. Kaˇzd´ y d-regul´ arn´ı strom m´ a nejv´ yˇse jeden vrchol, kter´ y nen´ı list a m´ a ménˇe neˇz d syn˚ u. Kdyˇz d-regul´ arn´ı strom m´ a n vrchol˚ u, pak jeho v´ yˇska je ⌈logd (n(d − 1) + 1)⌉. Nechˇt o je pˇrirozené oˇc´ıslov´ an´ı vrchol˚ u d-regul´ arn´ıho stromu. Kdyˇz pro vrchol v je o(v) = k, pak vrchol w je syn vrcholu v, pr´ avˇe kdyˇz o(w) ∈ {(k − 1)d + 2, (k − 1)d + 3, . . . , kd + 1}, a vrchol u je otcem vrcholu v, pr´ avˇe kdyˇz o(u) = 1 + ⌊ k−2 d ⌋. D˚ ukaz. Prvn´ı ˇcást tvrzen´ı plyne pˇr´ımo z poˇzadavku 2) na d-regul´ arn´ı strom. Má-li di k i regulárn´ı strom v´ yˇsku k, pak má alespoˇ n Σk−1 d + 1 a nejv´ y ˇ s e Σ d vrchol˚ u. Proto i=0 i=0 dk − 1 dk+1
1

,

dk − 1 < n(d − 1) ≤ dk+1 − 1

a zlogaritmován´ım dostaneme k < logd (n(d − 1) + 1) ≤ k + 1. Odtud plyne druhá ˇcást tvrzen´ı. Tˇret´ı ˇc´ ast pro ˇc´ısla syn˚ u dok´ aˇzeme indukc´ı podle oˇc´ıslován´ı. Synové koˇrene maj´ı ˇc´ısla 2, 3, . . . ,d + 1, protoˇze koˇren m´ a ˇc´ıslo 1. Kdyˇz tvrzen´ı plat´ı pro vrchol s ˇc´ıslem k, pak synové vrcholu s ˇc´ıslem k + 1 maj´ı ˇc´ısla kd + 2, kd + 3, . . . , kd + d + 1, coˇz odpov´ıdá ˇc´ısl˚ um (k + 1 − 1)d + 2, (k + 1 − 1)d + 3, . . . , (k + 1)d + 1, a tedy tvrzen´ı plat´ı. Posledn´ı ˇcást pak plyne z toho, ˇze kdyˇz i ∈ {(k − 1)d + 2, (k − 1)d + 3, . . . , kd + 1}, pak 1 + ⌊ i−2 d ⌋ = k. Číslování uzlů ve 2 reg. haldě:

Vˇsimnˇeme si, ˇze speciálnˇe pro d = 2 maj´ı synové vrcholu s ˇc´ıslem k ˇc´ısla 2k a 2k + 1 a otec vrcholu s ˇc´ıslem k má ˇc´ıslo ⌊ k2 ⌋. Tedy pro 2-regul´ arn´ı stromy je pˇredpis pro nalezen´ı syn˚ u a otce zvláˇstˇe jednoduch´ y.

Def:

ˇ Rekneme, ˇze mnoˇzina S s funkc´ı f je reprezentov´ ana d-regul´ arn´ı haldou H, kde H je d-regulárn´ı strom (T, r), kdyˇz pˇriˇrazen´ı prvk˚ u mnoˇziny S vrchol˚ um stromu T je bijekce splˇ nuj´ıc´ı podm´ınku (usp). Toto pˇriˇrazen´ı je realizov´ ano funkc´ı key, kter´ a vrcholu pˇriˇrazuje j´ım reprezentovan´ y prvek.

Přechod od d reg. str. k d reg. haldě:

Defince d-regulárn´ıho stromu umoˇzn ˇuje velmi efektivn´ı implementace d-regul´ arn´ıch hald. Mˇejme mnoˇzinu S reprezentovanou d-regul´ arn´ı haldou H s pˇrirozen´ ym oˇc´ıslován´ım o dregulárn´ıho stromu (T, r). Pak haldu H m˚ uˇzeme reprezentovat polem H[1..|S|], kde pro

3

Zjednodušené značení:

vrchol stromu v, pro kter´ y o(v) = i, je H(i) = (key(v), f (key(v)). Algoritmy budeme popisovat pro stromy, protoˇze je to názornˇejˇs´ı. Pˇreformulovat je pro pole je snadné (viz oˇc´ıslován´ı syn˚ u a otce vrcholu v). Pro jednoduchost budeme pro vrchol v ps´ at f (v) m´ısto f (key(v)), neboli f (v) bude oznaˇcovat f (s), kde s je reprezentov´ an vrcholem v. U d-regul´ arn´ıho stromu pˇredpokládáme, ˇze známe pˇrirozené oˇc´ıslov´ an´ı, a fr´ aze ‘posledn´ı vrchol’, ‘pˇredcházej´ıc´ı vrchol’ atd. se vztahuj´ı k tomuto oˇc´ıslov´ an´ı. Na to máme např. leftis haldy

Algoritmy

Operace UP & DOWN:

Pro d-regulárn´ı haldy nen´ı známa efektivn´ı implementace operace MERGE. Efektivn´ı implementace ostatn´ıch operac´ı jsou zaloˇzeny na pomocn´ ych operac´ıch UP(v) a DOWN(v). Operace UP(v) posunuje prvek s reprezentovan´ y vrcholem v smˇerem ke koˇreni, dokud vrchol reprezentuj´ıc´ı prvek s nesplˇ nuje podm´ınku (usp). Operace DOWN(v) je symetrická. UP(v): while v nen´ı koˇren a f (v) < f (otec(v)) do vymˇen ˇ key(v) a key(otec(v)) [vyměň uzly v a otec(v), tj. i hodnoty funkce f] v := otec(v) enddo DOWN(v): if v nen´ı list then w :=syn vrcholu v reprezentuj´ıc´ı prvek s nejmenˇs´ı hodnotou f (w) while f (w) < f (v) a v nen´ı list do vymˇen ˇ key(v) a key(w), v := w w :=syn vrcholu v reprezentuj´ıc´ı prvek s nejmenˇs´ı hodnotou f (w) enddo endif INSERT(s): v :=nov´ y posledn´ı list, key(v) := s, UP(v) MIN: V´ ystup:key(koˇren(T )) DELETEMIN: v :=posledn´ı list, r :=koˇren, key(r) := key(v) odstraˇ nv DOWN(r) DELETE(s): v :=vrchol reprezentuj´ıc´ı s [Toto je ve shode s predpokladem, ze dostaneme pro prvek na vstupu jeste informaci, jak prvek najit] w :=posledn´ı list t := key(w), key(v) := t, odstraˇ n w [Prohodime nas prvek s poslednim listem a pak UP nebo DOWN] if f (t) < f (s) then UP(v) else DOWN(v) endif [Neporovnavam s otcem prvku s!]

4

DECREASE(s, a): v :=vrchol reprezentuj´ıc´ı s f (s) := f (s) − a, UP(v) INCREASE(s, a): v :=vrchol reprezentuj´ıc´ı s f (s) := f (s) + a, DOWN(v) MAKEHEAP(S, f ): T := d-regulárn´ı strom s |S| vrcholy zvol libovolnou reprezentaci S vrcholy stromu T v :=posledn´ı vrchol, kter´ y nen´ı list while v je vrchol T do DOWN(v) v :=vrchol pˇredcházej´ıc´ı vrcholu v enddo Korektnost algoritmů:

Duální podmínka k (usp):

[libovolne umisti prvky S do stromu T (viz str. 38 (resp. 42) v Tarjan DS and Network algorithms)]

Ovˇeˇr´ıme korektnost algoritm˚ u. Je zˇrejmé, ˇze pomocné operace jsou korektn´ı – skonˇc´ı, kdyˇz podm´ınku (usp) splˇ nuje prvek s, kter´ y byl p˚ uvodnˇe reprezentov´ an vrcholem v. Korektnost operace MIN plyne pˇr´ımo z podm´ınky (usp), protoˇze koˇren reprezentuje nejmenˇs´ı prvek mnoˇziny S. U operace INSERT je podm´ınka (usp) splnˇena pro vˇsechny vrcholy s v´ yjimkou novˇe vytvoˇreného listu a operace UP zajist´ı jej´ı splnˇen´ı. Pˇri operaci DELETEMIN je podm´ınka (usp) splnˇena pro vˇsechny vrcholy s v´ yjimkou koˇrene a v tomto pˇr´ıpadˇe operace DOWN zajist´ı jej´ı splnˇen´ı. Po proveden´ı operac´ı DELETE(s), DECREASE(s, a) a INCREASE(s, a) je podm´ınka (usp) splnˇena pro vˇsechny vrcholy s v´ yjimkou vrcholu v a jej´ı splnˇen´ı opˇet zajist´ı operace UP resp. DOWN. Pro operaci MAKEHEAP budeme uvaˇzovat duáln´ı formulaci podm´ınky (usp): (d-usp) kdyˇz s je prvek reprezentovan´ y vrcholem v, pak f (s) ≤ f (t) pro vˇsechny prvky reprezentované syny vrcholu v. Pokud kaˇzd´ y vrchol splˇ nuje podm´ınku (d-usp), pak splˇ nuje i podm´ınku (usp). Zˇrejmˇe kaˇzd´ y list splˇ nuje podm´ınku (d-usp) a kdyˇz operace MAKEHEAP provede proceduru DOWN(v), pak je podm´ınka (d-usp) splnˇena pro vˇsechny vrcholy s ˇc´ısly alespoˇ n tak velk´ ymi jako je ˇc´ıslo v. Operace MAKEHEAP konˇc´ı proveden´ım operace DOWN na koˇren a odtud plyne jej´ı korektnost. Sloˇ zitost operac´ı Vypoˇcteme ˇcasovou sloˇzitost operac´ı: Jeden bˇeh cyklu v operaci UP vyˇzaduje ˇcas O(1) a v operaci DOWN ˇcas O(d). Proto operace UP v nejhorˇs´ım pˇr´ıpadˇe vyˇzaduje ˇcas O(logd |S|) a operace DOWN ˇcas O(d logd |S|). Operace MIN vyˇzaduje ˇcas O(1), INSERT a DECREASE vyˇzaduj´ı ˇcas O(logd |S|) a DELETEMIN, DELETE a INCREASE ˇcas O(d logd |S|).

Složitost MAKEHEAP:

Haldu m˚ uˇzeme vytvoˇrit iterac´ı operace INSERT, coˇz vyˇzaduje ˇcas O(|S| logd (|S|)). Ukáˇzeme, ˇze sloˇzitost operace MAKEHEAP je menˇs´ı, ale pro malé haldy je v´ yhodnˇejˇs´ı provádˇet opakovanˇe operaci INSERT. Operace DOWN(v) na vrchol ve v´ yˇsce h vyˇzaduje v neji horˇs´ım pˇr´ıpadˇe ˇcas O(hd). Vrchol˚ u v hloubce i je nejv´ yˇse d . Pˇredpokl´ adejme, ˇze strom Vzdálenost od kořene

Vzdálenost od nejhlubšího listu

5

má v´ yˇsku k, pak vrchol v hloubce i m´ a v´ yˇsku nejv´ yˇse k − i. Tedy operace MAKEHEAP Pk−1 i Pk−1 i+1 Pk−1 vyˇzaduje ˇcas O( i=0 d (k − i)d) = O( i=0 d (k − i)). Oznaˇcme A = i=0 di+1 (k − i), pak dA − A =

k−1 X

d

i+2

i=0

dk+1 +

(k − i) −

k X i=2

dk+1 + d2 k+1

k+1

d

k−1 X

d

i+1

i=0

(k − i) =

k+1 X i=2

i

d (k − i + 2) −

di (k − i + 2 − k + i − 1) − dk = dk+1 +

k X i=2

k X i=1

di (k − i + 1) =

di − dk =

k−1

−1 − dk. d−1

[Vydělím (d 1), protože dA

A = (d 1)A]

Zanedbáme

2

−d dk ze k = ⌈logd (|S|(d − 1) + 1)⌉, dost´ av´ ame, ˇze dk+12 ≤ Tedy A = dd−1 + d(d−1) 2 − d−1 . Protoˇ d2 ((d − 1)|S| + 1), a proto A ≤ 2d2 |S|. Tedy MAKEHEAP vyˇzaduje v nejhorˇs´ım pˇr´ıpadˇe jen ˇcas O(d2 |S|).

Aplikace Příklad #1:

Tˇr´ıdˇen´ı: prostou posloupnost ˇc´ısel x1 , x2 , . . . , xn lze setˇr´ıdit n´ asleduj´ıc´ım algoritmem pouˇz´ıvaj´ıc´ım haldu (f bude v tomto pˇr´ıpadˇe identick´ a funkce). d-HEAPSORT(x1 , x2 , . . . , xn ): MAKEHEAP({xi | i = 1, 2, . . . , n}, f ) i=1 while i ≤ n do yi :=MIN, DELETEMIN, i := i + 1 enddo V´ ystup: y1 , y2 , . . . , yn

Vhodné hodnoty d:

Příklad #2:

Teoreticky lze ukázat, ˇze pouˇzit´ı d-regul´ arn´ıch hald v algoritmu HEAPSORT pro d = 3 a d = 4 je v´ yhodnˇejˇs´ı neˇz d = 2. Experimenty uk´ azaly, ˇze optim´ aln´ı algoritmus pro posloupnosti délek do 1 000 000 by mˇel pouˇz´ıvat d = 6 nebo d = 7 (v experimentech byl mˇeˇren skuteˇcnˇe spotˇrebovan´ y ˇcas, nikoli poˇcet porovn´ an´ı a v´ ymˇen prvk˚ u). Pro delˇs´ı posloupnosti se optimáln´ı hodnota d m˚ uˇze zmenˇsit. ˇ sme následuj´ıc´ı Dalˇs´ım pˇr´ıkladem je nalezen´ı nejkratˇs´ıch cest v grafu z daného bodu. Reˇ u ´lohu: Vstup: orientovan´ y ohodnocen´ y graf (X, R, c), kde c je funkce z R do mnoˇziny kladn´ ych [funkce c: R > R+; cena cesty] reáln´ ych ˇc´ısel, a vrchol z ∈ X. ´ Ukol: nalézt pro kaˇzd´ y bod x ∈ X délku nejkratˇs´ı cestu ze z do x, kde délka cesty je souˇcet c-ohodnocen´ı hran na cestˇe. Dijkstr˚ uv algoritmus: d(z) := 0, U := {z} [d = distance; U je nějaká HALDA] for every x ∈ X \ {z} do d(x) := +∞ enddo [Zatím

je pro nás každý vrchol kromě kořene nedosažitelný]

6

while U 6= ∅ do najdi vrchol u ∈ U s nejmenˇs´ı hodnotou d(u) odstraˇ nuzU [Zkoušíme vylepšit for every (u, v) ∈ R do if d(u) + c(u, v) < d(v) then if d(v) = +∞ then vloˇz v do U endif d(v) := d(u) + c(u, v) endif enddo enddo Korektnost Dijkstrova algoritmu:

odhad nejkratší vzdálenosti do vrcholu v]

Korektnost algoritmu je zaloˇzena na kombinatorickém lemmatu, které ˇr´ık´ a, ˇze kdyˇz odstran ˇujeme z U prvek x s nejmenˇs´ı hodnotou d(x), pak vzd´ alenost ze z do x je pr´ avˇe d(x). Proto kdyˇz U = ∅, pak d(x) jsou délky nejkratˇs´ıch cest ze z do x pro vˇsechna x ∈ X. Tedy práce s mnoˇzinou U vyˇzaduje nejv´ yˇse |X| operac´ı INSERT, MIN a DELETEMIN a |R| operac´ı DECREASE a vˇzdy plat´ı |U | ≤ |X|. Vypoˇcteme ˇcasovou sloˇzitost Dijkstrova algoritmu za pˇredpokladu, ˇze U reprezentujeme jako d-regul´ arn´ı haldu. Kdyˇz d = 2, pak dostáváme, |R| ⌋}, pak ˇze algoritmus vyˇzaduje ˇcas O(|X| log(|X|) + |R| log(|X|)). Kdyˇz d = max{2, ⌊ |X| algoritmus vyˇzaduje ˇcas O(|R| logd |X|). V pˇr´ıpadˇe, ˇze (X, R) je hust´ y graf, tj. |R| > |X|1+ε pro ε > 0, pak logd |X| = O(1) a algoritmus je line´ arn´ı (tj. vyˇzaduje ˇcas O(|R|)).

III. Leftist haldy Dalˇs´ım typem hald, se kter´ ymi se sezn´ am´ıme, jsou lefist haldy (nezn´ ame vhodn´ y ˇcesk´ y pˇreklad, proto z˚ ustáváme u anglického n´ azvu). Je to velmi elegantn´ı a jednoduch´ y typ hald. Vˇsechny operace jsou stejnˇe jako u regul´ arn´ıch hald zaloˇzeny na dvou základn´ıch operac´ıch, z nichˇz v tomto pˇr´ıpadˇe hlavn´ı je MERGE a druhou je DECREASE. Pouˇzit´ı MERGE pˇri návrhu jin´ ych operac´ı je bˇeˇzné i v dalˇs´ıch hald´ ach. Operace MERGE vyuˇz´ıvá speciáln´ıch vlastnost´ı leftist hald a idea operace DECREASE je stejná jako ve Fibonacciho haldách. Nejprve form´ alnˇe pop´ıˇseme strukturu leftist hald. Definice hodnoty npl:

Definice Leftist haldy:

Mˇejme binárn´ı koˇrenov´ y strom (T, r) (to znamen´ a, ˇze r je koˇren, kaˇzd´ y vrchol má nejv´ yˇse dva syny a u kaˇzdého syna v´ıme, zda je to prav´ y nebo lev´ y syn). Pro vrchol v oznaˇcme npl(v) délku nejkratˇs´ı cesty z v do vrcholu, kter´ y m´ a nejv´ yˇse jednoho syna, takˇze napˇr. pro list l plat´ı npl(l) = 0. Mˇejme S ⊆ U a funkci f : S − → R. Pak bin´ arn´ı strom (T, r) takov´ y, ˇze (1) kdyˇz vrchol v má jen jednoho syna, pak je to lev´ y syn, (2) kdyˇz vrchol v má dva syny, pak

npl(prav´ y syn v) ≤ npl(lev´ y syn v), (3) existuje jednoznaˇcné pˇriˇrazen´ı prvk˚ u S vrchol˚ um T , které splˇ nuje podm´ınku (usp) (toto pˇriˇrazen´ı je reprezentov´ ano funkc´ı key, kter´ a vrcholu v pˇriˇrad´ı prvek z mnoˇziny S reprezentovan´ y vrcholem v) je leftist halda reprezentuj´ıc´ı mnoˇzinu S a funkci f .

7

Struktura vrcholu:

Def:

Struktura vrcholu v v leftist haldˇe: S vrcholem v jsou spojeny ukazatelé otec(v), levy(v) a pravy(v) na otce a na levého a pravého syna vrcholu v. Kdyˇz ukazatel nen´ı definov´ an, pak p´ıˇseme, ˇze jeho hodnota je N IL. Dále jsou s vrcholem spojeny funkce npl(v) – promˇenná s hodnotou npl(v), key(v) – prvek reprezentovan´ y vrcholem v, f (v) – promˇenná obsahuj´ıc´ı hodnotu f (key(v)). Uvedeme základn´ı vlastnost leftist haldy, kter´ a umoˇzn ˇuje efektivn´ı implementace operac´ı. Posloupnost vrchol˚ u v0 , v1 , . . . , vk se naz´ yv´ a prav´ a cesta z vrcholu v, kdyˇz v = v0 , vi+1 je prav´ y syn vi pro kaˇzdé i = 0, 1, . . . , k − 1 a vk nem´ a pravého syna. Pak podstrom vrcholu v do hloubky k je u ´pln´ y binárn´ı strom a m´ a tedy alespoˇ n 2k+1 − 1 vrchol˚ u. Proto plat´ı Tvrzen´ı. V leftist haldˇe je délka pravé cesty z kaˇzdého vrcholu v nejv´ yˇse rovna log(velikost podstromu urˇceného vrcholem v).

Algoritmy a sloˇ zitost operac´ı Základn´ı operac´ı pro leftist haldy je MERGE. Tato operace je definov´ ana rekurzivnˇe a hloubka rekurze je omezena právˇe délkami prav´ ych cest. MERGE(T1 , T2 ): if T1 = ∅ then V´ ystup= T2 konec endif if T2 = ∅ then V´ ystup= T1 konec endif if key(koˇren T1 ) > key(koˇren T2 ) then [Výsledná halda musí splňovat podmínku (usp), bez zamˇen ˇ T1 a T2 této záměny by podmínka nemusela být splněná!!] endif T ′ :=MERGE(podstrom pravého syna koˇrene T1 , T2 ) Připojím strom T' pravy(koˇren T1 ) := koˇren T ′ ′ otec(koˇren T ) := koˇren T1 if npl(pravy(koˇren T1 )) > npl(levy(koˇren T1 )) then Udržujeme platnou definici Leftist vymˇen ˇ levého a pravého syna koˇrene T1 endif Opravím si hodnotu npl npl(koˇren T1 ) := npl(pravy(koˇren T1 ))+ 1 INSERT(x): Vytvoˇr haldu T1 reprezentuj´ıc´ı {x} MERGE(T, T1 ) MIN: V´ ystup: key(koˇren T ) DELETEMIN: T1 :=podstrom levého syna koˇrene T T2 :=podstrom pravého syna koˇrene T MERGE(T1 , T2 )

haldy

8

MAKEHEAP(S, f ): Q :=prázdná fronta for every s ∈ S do vloˇz leftist haldu Ts reprezentuj´ıc´ı {s} do Q enddo while |Q| > 1 do vezmi haldy T1 a T2 z vrcholu Q (odstraˇ n je) MERGE(T1 , T2 ) vloˇz do Q enddo Časové složitosti:

Složitost MAKEHEAP:

Pozn:

Implementace DECREASE a INCREASE:

Operace OPRAV:

Vytvořím jednoprvkové haldy

Postupně spojuji tyto haldy až mi zůstane jediná

Vypoˇcteme ˇcasovou sloˇzitost pˇredchoz´ıch algoritm˚ u. Kaˇzd´ y bˇeh algoritmu MERGE (bez rekurzivn´ıho volán´ı) vyˇzaduje ˇcas O(1). Poˇcet rekurzivn´ıch vol´ an´ı je souˇcet délek prav´ ych cest, proto algoritmus MERGE vyˇzaduje ˇcas O(log(|S1 |+|S2 |)), kde Si je mnoˇzina reprezentovaná haldou Ti pro i = 1, 2. Odtud d´ ale plyne, ˇze ˇcas algoritm˚ u INSERT a DELETEMIN je v nejhorˇs´ım pˇr´ıpadˇe O(log(|S|)). Operace MIN vyˇzaduje ˇcas O(1). Pro odhad sloˇzitosti MAKEHEAP budeme uvaˇzovat, ˇze na zaˇc´ atku algoritmu je na vrcholu fronty speciáln´ı znak, kter´ y se jen pˇrenese na konec fronty. Odhadneme ˇcas, kter´ y spotˇrebuj´ı while-cykly mezi dvˇema pˇrenesen´ımi speci´ aln´ıho znaku. Pˇredpokl´ adejme, ˇze se speciáln´ı znak pˇrenesl po k-té. V tomto okamˇziku maj´ı vˇsechny haldy ve frontˇe aˇz na jednu velikost hald a jelikoˇz jedna operace MERGE vyˇzaduje O(k) ˇcasu, 2k−1 . Proto ve frontˇe Q je 2|S| k−1 uˇzeme tedy shrnout, ˇze operace MAKEHEAP tak while-cykly vyˇzaduj´ı ˇcas O(k 2|S| k−1 ). M˚ potˇrebuje ˇcas ∞ ∞ X X |S| k O( k k−1 ) = O(|S| ) = O(|S|). k−1 2 2 k=1 k=1 Viz pozn. níže P ∞ k ˇ Rada r. podle pod´ılového d’Alambertova kritéria a lze jednoduˇse k=1 2k−1 konverguje napˇ spoˇc´ıtat (napˇr. stejnou metodou jako pro regul´ arn´ı haldy), ˇze souˇcet je 4. Implementace operac´ı DECREASE a INCREASE pomoc´ı operac´ı UP a DOWN jako v d-regulárn´ıch haldách nen´ı efektivn´ı, protoˇze délka cesty z koˇrene do listu v leftist haldˇe m˚ uˇze b´ yt aˇz |S|. Proto navrhneme pro tyto operace efektivnˇejˇs´ı algoritmus zaloˇzen´ y na jiném principu. Tento princip je pak pouˇzit i pro Fibonacciho haldy. Nejprve pop´ıˇseme pomocnou operaci Oprav(T, v), kter´ a vytvoˇr´ı leftist haldu z binárn´ıho ′ stromu T vzniklého z leftist haldy T odtrˇzen´ım podstromu s koˇrenem ve vrcholu v. Oprav(T, v): t := otec(v), npl(t) := 0 [Zde opravuji strom T (konkrétně otce t uzlu v), ze kterého škubu if pravy(t) 6= v then levy(t) := pravy(t) endif Uzel t nesmí mít pouze pravého syna pravy(t) := N IL while se zmenˇsilo npl(t) a t nen´ı koˇren do Směrem ke kořeni opravuji hodnoty npl t := otec(t) if npl(pravy(t)) > npl(levy(t)) then vymˇen ˇ levy(t) a pravy(t) endif npl(t) := npl(pravy(t)) + 1 enddo Výstup: t

v.]

9 Korektnost procedury OPRAV:

Po proveden´ı operace Oprav maj´ı vˇsechny vrcholy spr´ avné ˇc´ıslo npl a podm´ınky kladené na leftist haldu jsou splnˇeny. Tedy po proveden´ı Oprav je T opˇet leftist halda. Kdyˇz t je posledn´ı vrchol, u kterého se zmenˇsilo npl, pak vˇsechny vrcholy, kde se zmenˇsilo npl, tvoˇr´ı pravou cestu z vrcholu t. To znamen´ a, ˇze while-cyklus se prov´ adˇel nejv´ yˇse log(|S|)krát a kaˇzd´ y bˇeh while-cyklu vyˇzadoval ˇcas O(1). Proto algoritmus Oprav vyˇzaduje ˇcas O(log(|S|)). Pop´ıˇseme ostatn´ı algoritmy. DECREASE(s, a): v :=prvek reprezentuj´ıc´ı s T1 :=podstrom T urˇcen´ y vrcholem v, f (v) := f (v) − a T2 :=Oprav(T, v), T :=MERGE(T1 , T2 ) INCREASE(s, a): v :=prvek reprezentuj´ıc´ı s y vrcholem levy(v) T1 :=podstrom T urˇcen´ T2 :=podstrom T urˇcen´ y vrcholem pravy(v) T3 :=leftist halda reprezentuj´ıc´ı prvek s f (v) := f (v) + a, T4 :=Oprav(T, v), T1 :=MERGE(T1 , T3 ) T2 :=MERGE(T2 , T4 ), T :=MERGE(T1 , T2 ) DELETE(s, a): v :=prvek reprezentuj´ıc´ı s T1 :=podstrom T urˇcen´ y vrcholem levy(v) T2 :=podstrom T urˇcen´ y vrcholem pravy(v) T3 :=MERGE(T1 , T2 ), T4 :=Oprav(T, v) T :=MERGE(T3 , T4 ) Protoˇze algoritmy MERGE a Oprav vyˇzaduj´ı ˇcas O(log(|S|) a protoˇze zbylé ˇcásti algoritm˚ u pro operace DECREASE, INCREASE a DELETE vyˇzaduj´ı O(1) ˇcasu, m˚ uˇzeme shrnout v´ ysledky: Vˇ eta. V leftist hald´ ach existuje implementace operace MIN, kter´ a v nejhorˇs´ım pˇr´ıpadˇe vyˇzaduje ˇcas O(1), implementace operac´ı INSERT, DELETEMIN, DELETE, MERGE, DECREASE a INCREASE, které vyˇzaduj´ı v nejhorˇs´ım pˇr´ıpadˇe ˇcas O(log(|S|)), a implementace operace MAKEHEAP, kter´ a vyˇzaduje ˇcas O(|S|), kde S je reprezentovan´ a mnoˇzina.

IV. Amortizovan´ a sloˇzitost Pop´ıˇseme bankovn´ı paradigma pro poˇc´ıt´ an´ı s amortizovanou sloˇzitost´ı. Pˇredpokládejme, ˇze máme funkci h, která ohodnucuje konfigurace a kvantitativnˇe vystihuje jejich vhodnost pro proveden´ı operace o. Kdyˇz na konfiguraci D aplikujeme operaci o a dostaneme konfiguraci D′ , pak amortizovaná sloˇzitost am(o) operace o m´ a vystihovat nejen ˇcasovou nároˇcnost operace, ale i to, jak se zmˇenila vhodnost konfigurace pro tuto operaci. Proto ji definujme jako am(o) = t(o) + h(D′ ) − h(D), kde t(o) je ˇcas potˇrebn´ y pro proveden´ı operace o.

10

Pˇredpokládejme, ˇze chceme provést posloupnost operac´ı o1 , o2 , . . . , on na konfiguraci D0 . Znázorn´ıme si to takto: o1 o2 o3 on D0 −→ D1 −→ D2 −→ . . . −→ Dn . Pˇredpokládejme, ˇze pro kaˇzdé i = 1, 2, . . . , n m´ ame odhad c(oi ) amortizované sloˇzitosti operace oi , tj. am(oi ) ≤ c(oi ) pro vˇsechna i = 1, 2, . . . , n. Pak n X

am(oi ) =

i=1

n X i=1

Z toho plyne, ˇze

n n X X t(oi ) + h(Di ) − h(Di−1 ) = h(Dn ) − h(D0 ) + t(oi ) ≤ c(oi ). i=1

n X i=1

t(oi ) ≤

n X i=1

i=1

c(oi ) − h(Dn ) + h(D0 ).

Obvykle je h(D) ≥ 0 pro vˇsechny konfigurace D nebo naopak h(D) ≤ 0 pro vˇsechny konfigurace D. Kdyˇz h(D) ≥ 0, pak n X i=1

kdyˇz h(D) ≤ 0, pak

n X i=1

t(oi ) ≤

n X

c(oi ) + h(D0 ),

t(oi ) ≤

n X

c(oi ) − h(Dn ).

i=1

i=1

To znamená, ˇze odhad amortizované sloˇzitosti d´ av´ a také odhad na ˇcasovou sloˇzitost posloupnosti operac´ı, kter´ y b´ yvá lepˇs´ı neˇz odhad sloˇzitosti v nejhorˇs´ım pˇr´ıpadˇe. Tato skuteˇcnost vysvˇetluje ˇradu pˇr´ıpad˚ u, kdy v´ ysledky byly lepˇs´ı neˇz teoretick´ y v´ ypoˇcet. Ukazuje se, ˇze sloˇzitost posloupnosti operac´ı v nejhorˇs´ım pˇr´ıpadˇe je ˇcasto podstatnˇe menˇs´ı neˇz souˇcet sloˇzitost´ı v nejhorˇs´ım pˇr´ıpadˇe pro jednotlivé operace.

V. Binomi´ aln´ı haldy Dalˇs´ı typ hald je motivován sˇc´ıtan´ım pˇrirozen´ ych ˇc´ısel. Binomi´ aln´ı halda reprezentuj´ıc´ı n−prvkovou mnoˇzinu se totiˇz chov´ a podobnˇe jako ˇc´ıslo n. Tento typ hald je také po zobecnˇen´ı v jistém smyslu vzorem pro Fibonacciho haldy. Def:

Pro i = 0, 1, . . . definujeme rekurentnˇe binomi´ aln´ı stromy Hi . Jsou to koˇrenové stromy takové, ˇze H0 je jednoprvkov´ y strom a strom Hi+1 vznikne ze dvou disjunktn´ıch strom˚ u Hi , kde koˇren jednoho stromu se stane dalˇs´ım synem (nejlevˇejˇs´ım nebo nejpravˇejˇs´ım) koˇrene druhého stromu. Viz Obr. 1. Nejprve uvedeme základn´ı vlastnosti tˇechto strom˚ u. Tvrzen´ı. Pro kaˇzdé pˇrirozené ˇc´ıslo i = 0, 1, . . . plat´ı: (1) strom Hi m´ a 2i vrchol˚ u, (2) koˇren stromu Hi m´ a i syn˚ u, (3) délka nejdelˇs´ı cesty z koˇrene do listu ve stromu Hi je i (tj. v´ yˇska Hi je i), (4) podstromy urˇcené syny koˇrene stromu Hi jsou izomorfn´ı se stromy H0 , H1 , . . . , Hi−1 .

11

H0

H1

H2 Hi Hi Hi+1

H3 Obr. 1

D˚ ukaz. Tvrzen´ı plat´ı pro strom H0 a jednoduchou indukc´ı se dok´ aˇze i pro dalˇs´ı stromy. i i i+1 Skuteˇcnˇe, kdyˇz Hi má 2 vrchol˚ u, pak Hi+1 m´ a 2(2 ) = 2 vrchol˚ u. Koˇren stromu Hi+1 má o jednoho syna v´ıce neˇz koˇren stromu Hi a nejdelˇs´ı cesta do listu je o 1 delˇs´ı. Protoˇze podstrom syna, kter´ y pˇribyl koˇreni stromu Hi+1 , je izomorfn´ı s Hi a jinak se nic nemˇenilo, je d˚ ukaz kompletn´ı. Binomiáln´ı halda H reprezentuj´ıc´ı mnoˇzinu S je soubor (seznam) strom˚ u {T1 , T2 , . . . , Tk } takov´ y, ˇze celkov´ y poˇcet vrchol˚ u v tˇechto stromech je roven velikosti S a existuje a je dáno jednoznaˇcné pˇriˇrazen´ı prvk˚ u z S vrchol˚ um strom˚ u takové, ˇze plat´ı podm´ınka (usp) – toto pˇriˇrazen´ı je realizováno funkc´ı key, kter´ a vrcholu stromu pˇriˇrazuje prvek j´ım reprezentovan´ y; kaˇzd´ y strom Ti je izomorfn´ı s nˇejak´ ym stromem Hj ; Ti nen´ı izomorfn´ı s ˇzádn´ ym Tj pro i 6= j. Vztah bin. čísel a binom. hald:

Z binárn´ıho zápisu pˇrirozen´ ych ˇc´ısel plyne, ˇze pro kaˇzdé pˇrirozené ˇc´ıslo n > 0 existuje Pk prostá posloupnost i1 , i2 , . . . , ik pˇrirozen´ ych ˇc´ısel takov´ a, ˇze n = j=1 2ij . Z toho plyne, ˇze pro kaˇzdou neprázdnou mnoˇzinu S existuje binomi´ aln´ı halda reprezentuj´ıc´ı S. Tato halda obsahuje strom izomorfn´ı s Hi , pr´ avˇe kdyˇz v bin´ arn´ım z´ apise ˇc´ısla |S| je na i-tém m´ıstˇe zprava 1. Algoritmy a sloˇ zitost operac´ı Operace pro binomiáln´ı haldy jsou stejnˇe jako pro leftist haldy zaloˇzeny na operaci MERGE. Operace MERGE pro binomiáln´ı haldy je analogi´ı sˇc´ıt´ an´ı pˇrirozen´ ych ˇc´ısel v binárn´ım zápise. MERGE(H1 , H2 ): (komentáˇr: Hi reprezentuje mnoˇzinu Si pro i = 1, 2 a S1 ∩ S2 = ∅)

12

i := 0, T :=prázdn´ y strom, H := ∅ while i < log(|S1 | + |S2 |) do if existuje U ∈ H1 izomorfn´ı s Hi then Existuje v první haldě strom izomorfní s H_i? (Tzn. stačí projít stromy T_i haldy a hledat U1 := U index i) else U1 :=prázdn´ y strom endif if existuje U ∈ H2 izomorfn´ı s Hi then U2 := U else U2 :=prázdn´ y strom endif case (existuje právˇe jeden neprázdn´ y strom V ∈ {T, U1 , U2 }) do: [Našli jsme H_i pouze v jedné z hald a nezůstalo nám nic z vloˇz V do H, T :=prázdn´ y strom předchozího spojování] (existuj´ı právˇe dva neprázdné stromy V1 , V2 ∈ {T, U1 , U2 }) do: T :=spoj(V1 , V2 ) (vˇsechny stromy T , U1 a U2 jsou nepr´ azdné) do: vloˇz T do H, T :=spoj(U1 , U2 ) endcase i := i + 1 enddo if T 6=prázdn´ y strom then vloˇz T do H endif V´ ystup:H spoj(T1 , T2 ): if f (koˇren T1 ) > f (koˇren T2 ) then vymˇen ˇ stromy T1 a T2 endif vytvoˇr nového syna v koˇrene T1 v :=koˇren T2 Výstup: Kořen T_1 Korektnost MERGE:

Je vidˇet, ˇze kdyˇz oba stromy T1 a T2 jsou izomorfn´ı s Hi , pak v´ ysledn´ y strom operace spoj je izomorfn´ı s Hi+1 . Korektnost operace MERGE plyne z tohoto pozorov´ an´ı a z faktu, ˇze Hj obsahuje strom izomorfn´ı s Hi , pr´ avˇe kdyˇz v bin´ arn´ım z´ apise ˇc´ısla |Sj | je na i-tém m´ıstˇe zprava 1, a ˇze T je neprázdn´ y strom, kdyˇz se prov´ ad´ı posun ˇr´ adu pˇri sˇc´ıt´ an´ı. Protoˇze kaˇzd´ y bˇeh cyklu vyˇzaduje ˇcas O(1), algoritmus MERGE vyˇzaduje ˇcas O(log(|S1 | + |S2 |)). Implementace dalˇs´ıch algoritm˚ u je podobn´ a jako pro leftist haldy. INSERT(x): Vytvoˇr haldu H1 reprezentuj´ıc´ı {x} MERGE(H, H1 ) MIN: Prohledej prvky reprezentované koˇreny vˇsech strom˚ uvH V´ ystup: nejmenˇs´ı z tˇechto prvk˚ u

13

DELETEMIN: Prohledej prvky reprezentované koˇreny vˇsech strom˚ uvH T := strom, jehoˇz koˇren reprezentuje nejmenˇs´ı prvek H1 := H \ {T } H2 := halda tvoˇrená podstromy T urˇcen´ ymi syny koˇrene T MERGE(H1 , H2 ) Korektnost MIN operace:

Operace INCREASE a DECREASE:

Časová slož. MERGE:

Časová slož. MIN a DELMIN:

Časová slož. DECREASE a INCREASE:

Z podm´ınky (usp) je zˇrejmé, ˇze nejmenˇs´ı prvek v S je reprezentov´ an v koˇreni nˇejakého stromu haldy. T´ım je dána korektnost operace MIN. Z u ´vodn´ıho tvrzen´ı plyne, ˇze H2 v operaci DELETEMIN je binomi´ aln´ı halda, a odtud plyne korektnost operace DELETEMIN. Operace DECREASE se implementuje pomoc´ı operace UP a operace INCREASE pomoc´ı operace DOWN stejnˇe jako v regul´ arn´ıch hald´ ach. Struktura binomiáln´ı haldy nepodporuje pˇr´ımo operaci DELETE – ta se d´ a realizovat jedinˇe jako posloupnost operac´ı DECREASE(s, ∞) a DELETEMIN. Operace MAKEHEAP se provád´ı opakován´ım operace INSERT. V´ ypoˇcet ˇcasové sloˇzitosti operac´ı pro binomi´ aln´ı haldy vyuˇz´ıv´ a nˇekolik zn´ am´ ych fakt˚ u. Operace MERGE simuluje sˇc´ıtán´ı pˇrirozen´ ych ˇc´ısel v bin´ arn´ım z´ apise a m´ a tedy stejnou sloˇzitost. Odhad sloˇzitosti vytváˇren´ı haldy vyuˇz´ıv´ a zn´ amého faktu, ˇze amortizovaná sloˇzitost pˇriˇc´ıtán´ı 1 k binárn´ımu ˇc´ıslu je O(1). Odhad sloˇzitosti operac´ı MIN a DELETEMIN je zaloˇzen na pozorován´ı, ˇze binomiáln´ı halda reprezentuj´ıc´ı mnoˇzinu S m´ a tolik strom˚ u, kolik je jedniˇcek v binárn´ım zápise |S|, a to je nejv´ yˇse log(|S|).

Z tvrzen´ı také plyne, ˇze v´ yˇska vˇsech strom˚ u v binomi´ aln´ı haldˇe je ≤ log(|S|) a poˇcet syn˚ u koˇrene kaˇzdého stromu je také ≤ log(|S|), pˇriˇcemˇz tento odhad se ned´ a zlepˇsit. Odtud dostáváme sloˇzitost operac´ı DECREASE a INCREASE v nejhorˇs´ım pˇr´ıpadˇe. M˚ uˇzeme tedy shrnout:

Vˇ eta. Pro binomi´ aln´ı haldy algoritmy operac´ı INSERT, MIN, DELETEMIN, DECREASE a MERGE vyˇzaduj´ı ˇcas O(log(|S|)), algoritmus operace INCREASE vyˇzaduje ˇcas O(log2 (|S|)) a algoritmus operace MAKEHEAP ˇcas O(|S|). Neefektivnost Binom. hald:

Z tˇechto v´ ysledk˚ u je vidˇet, ˇze pˇredchoz´ı typy hald maj´ı efektivnˇejˇs´ı chov´ an´ı neˇz binomiáln´ı haldy. V´ yznam binomiáln´ıch hald tak spoˇc´ıv´ a pˇredevˇs´ım v tom, ˇze se daj´ı d´ ale zobecnit (t´ımto zobecnˇen´ım jsou Fibonacciho haldy) a ˇze na nich lze kr´ asnˇe ilustrovat princip, ˇze s ˇradou u ´prav je v´ yhodné poˇckat a neprov´ adˇet je okamˇzitˇe. ´ implentace operac´ı L´ına Následuj´ıc´ı algoritmy jsou zaloˇzeny na ideji, ˇze ‘vyvaˇzov´ an´ı’ staˇc´ı prov´ adˇet jen pˇri operac´ıch MIN a DELETEMIN, kdy je stejnˇe zapotˇreb´ı prohledat vˇsechny stromy. Z tohoto d˚ uvodu zeslab´ıme podm´ınky na binomiáln´ı haldy.

Def:

u {T1 , T2 , . . . , Tk } takov´ y, L´ıná binomiáln´ı halda H reprezentuj´ıc´ı mnoˇzinu S je seznam strom˚ ˇze celkov´ y poˇcet vrchol˚ u v tˇechto stromech je roven velikosti S a existuje jednoznaˇcné pˇriˇrazen´ı prvk˚ u mnoˇziny S vrchol˚ um strom˚ u, které splˇ nuje podm´ınku (usp) – toto pˇriˇrazen´ı je jako obvykle realizov´ ano funkc´ı key; kaˇzd´ y strom Ti je izomorfn´ı s nˇejak´ ym stromem Hj . Stejné podmínky jako u binom. hald, pouze jedna podmínka byla odebrána. Zmizela podminka ohledne vylouceni dvou izomorfnich stromu v H.

14 Pozn. k definici:

V l´ıné binomiáln´ı haldˇe je vynech´ an pˇredpoklad neizomorfnosti strom˚ u tvoˇr´ıc´ıch haldu. Tento fakt se projev´ı ve velmi jednoduchém algoritmu pro operaci MERGE. MERGE(H1 , H2 ): ˇ konkatenaci seznam˚ Proved u H1 a H2

INSERT:

#1

#2

Samotn´ y algoritmus pro operaci INSERT se nezmˇen´ı, jen provede tuto implementaci operace MERGE. Operace MIN a DELETEMIN pouˇzij´ı n´ asleduj´ıc´ı pomocnou proceduru vyvaz. Jej´ım vstupem je soubor seznam˚ u {Oi | i = 0, 1, . . . , k}, kde seznam Oi obsahuje jen stromy izomorfn´ı se stromem Hi . Procedura vyvaz pak z tˇechto strom˚ u vytvoˇr´ı klasickou binomiáln´ı haldu. vyvaz({Oi | i = 0, 1, . . . , k}): i := 0, H := ∅ while existuje Oi 6= ∅ do [For cyklus] while |Oi | > 1 do vezmi dva r˚ uzné stromy T1 a T2 z Oi odstraˇ n je z Oi spoj(T1 , T2 ) vloˇz do Oi+1 enddo if Oi 6= ∅ then strom T ∈ Oi odstraˇ n z Oi a vloˇz do H endif, i := i + 1 enddo V´ ystup: H

Spojujeme stromy v O_i a tím z nich efektivně vytváříme stromy pro seznam O_{i+1}.

MIN: Prohledej prvky reprezentované koˇreny vˇsech strom˚ uvH MIN operace, jak jsme definovali poprvé. V´ ystup: nejmenˇs´ı z tˇechto prvk˚ u stromy rozdˇel do mnoˇzin Oi = {vˇsechny stromy v H izomorfn´ı s Hi } vyvaz({Oi | i = 0, 1, . . . , ⌊log(|S|)⌋})

ji

DELETEMIN: Prohledej prvky reprezentované koˇreny vˇsech strom˚ uvH T := strom, jehoˇz koˇren reprezentuje nejmenˇs´ı prvek stromy rozdˇel do mnoˇzin Oi = {vˇsechny stromy v H izomorfn´ı s Hi r˚ uzné od T }∪{podstrom T urˇcen´ y nˇejak´ ym synem koˇrene T izomorfn´ı s Hi } vyvaz({Oi | i = 0, 1, . . . , ⌊log(|S|)⌋}) Časové složitosti:

ˇ Casov´ a sloˇzitost operac´ı INSERT a MERGE pˇri l´ıné implementaci je O(1), ale ˇcasová sloˇzitost operac´ı MIN a DELETEMIN je v nejhorˇs´ım pˇr´ıpadˇe O(|S|). Tento odhad je velmi ˇspatn´ y, ale ukáˇzeme, ˇze amortizovan´ a sloˇzitost m´ a rozumné hodnoty. Pˇripom´ınáme, ˇze amortizovaná sloˇzitost je ˇcas operace plus ohodnocen´ı v´ ysledné struktury minus ohodnocen´ı poˇcáteˇcn´ı struktury. Konfiguraci ohodnot´ıme poˇctem strom˚ u v haldˇe. Protoˇze operace MERGE nemˇen´ı poˇcet strom˚ u a protoˇze operace INSERT pˇrid´ a jen jeden strom, je

15

Amortizovaná složitost MIN a DELMIN:

amortizovaná sloˇzitost operac´ı MERGE a INSERT st´ ale O(1). Uk´ aˇzeme, ˇze amortizovaná sloˇzitost operac´ı MIN a DELETEMIN pˇri l´ıné implementaci binomi´ aln´ıch hald je O(log(|S|). Protoˇze kaˇzd´ y bˇeh vnitˇrn´ıho while-cyklu v operaci vyvaz vyˇzaduje ˇcas O(1) a Pk zmenˇs´ı poˇcet strom˚ u v seznamech Oi o 1, operace vyvaz vyˇzaduje ˇcas O(k + i=0 |Oi |).= Operace MIN bez podprocedury vyvaz vyˇzaduje ˇcas O(|H|) a operace DELETEMIN bez podprocedury vyvaz ˇcas O(H + i) pro takové i, ˇze T je izomorfn´ı s Hi . Podle tvrzen´ı je i ≤ log(|S|), a tedy operace MIN vyˇzaduje ˇcas O(|H|) a operace DELETEMIN ˇcas O(|H| + log(|S|)). Protoˇze ohodnocen´ı klasické binomi´ aln´ı haldy je nejv´ yˇse log(|S|) (obsahuje tolik strom˚ u, kolik je 1 v bin´ arn´ım z´ apise ˇc´ısla |S|), dost´ av´ ame, ˇze amortizovaná sloˇzitost operace MIN je O(|H| − |H| + log(|S|)) = O(log(|S|)) a amortizovaná sloˇzitost operace DELETEMIN je O(|H| + log(|S|) − |H| + log(|S|)) = O(log(|S|)). Protoˇze si funkci ohodnocen´ı vol´ıme, m˚ uˇzeme pouˇz´ıt takové multiplikativn´ı koeficienty, aby jednotka ˇcasu odpov´ıdala jednotce v amortizované sloˇzitosti. Proto lze |H| od sebe odeˇc´ıst.

VI. Fibonacciho haldy V´ yznam Fibonacciho hald urˇcuje fakt, ˇze amortizovan´ a sloˇzitost operac´ı INSERT a DECREASE v tˇechto haldách je O(1) a amortizovan´ a sloˇzitost operace DELETEMIN je O(log(|S|). Proto se hodnˇe pouˇz´ıvaj´ı v grafov´ ych algoritmech, kde umoˇzn ˇuj´ı v mnoha pˇr´ıpadech dosáhnout asymptoticky témˇeˇr line´ arn´ı sloˇzitosti. Nezn´ ame vˇsak ˇzádné experimentáln´ı v´ ysledky, které by porovn´ avaly pouˇzit´ı Fibonacciho hald a napˇr. d-regulárn´ıch hald v tˇechto grafov´ ych algoritmech v praxi. Takˇze nezn´ ame podm´ınky, za kter´ ych jsou Fibonacciho haldy lepˇs´ı neˇz tˇreba d-regul´ arn´ı haldy, ani nev´ıme, do jaké m´ıry je to jen teoretick´ y v´ ysledek a do jaké m´ıry jsou opravdu prakticky pouˇzitelné. Neformálnˇe ˇreˇceno, je Fibonacciho halda mnoˇzina strom˚ u, jejichˇz nˇekteré vrcholy r˚ uzné od koˇren˚ u jsou oznaˇceny, a kde existuje jednoznaˇcn´ a korepondence mezi prvky S a vrcholy strom˚ u (realizována funkc´ı key), kter´ a splˇ nuje podm´ınku (usp). Toto je vˇsak jen pˇribliˇzné vyjádˇren´ı. Existuj´ı totiˇz struktury, na které se tento popis hod´ı, ale nevznikly z prázdné Fibonacciho haldy aplikac´ı posloupnosti haldov´ ych operac´ı. Pˇritom d˚ ukaz efektivity Fibonacciho hald se dosti v´ yraznˇe op´ır´ a o fakt, ˇze halda vznikla z pr´ azdné haldy aplikac´ı algoritm˚ u pro Fibonacciho haldy. Proto nejprve pop´ıˇseme algoritmy pro tyto operace, a pak budeme definovat Fibonacciho haldy jako struktury vzniklé z pr´ azdné haldy aplikac´ı posloupnosti tˇechto algoritm˚ u. Algoritmy Označování vrcholů:

Def:

V algoritmech pˇredpokládáme, ˇze Fibonacciho halda je seznam strom˚ u, kde nˇekteré vrcholy r˚ uzné od koˇren˚ u jsou oznaˇceny. Vrchol je oznaˇcen, pr´ avˇe kdyˇz nen´ı koˇren a kdyˇz mu byl nˇekdy dˇr´ıve odtrˇzen nˇekter´ y jeho syn. Toto se nezaznamen´ av´ a pro koˇreny strom˚ u. Proto kdyˇz se vrchol stane koˇrenem (odtrˇzen´ım podstromu urˇceného t´ımto vrcholem), zapomene se ˇ tento u ´daj a zaˇcne se znovu zaznamen´ avat, aˇz kdyˇz vrchol pˇrestane b´ yt koˇrenem. Rekneme, ˇze strom má rank i, kdyˇz jeho koˇren m´ a i syn˚ u. Tento fakt nahrazuje test pouˇz´ıvan´ y v binomiáln´ıch haldách, ˇze strom je izomorfn´ı se stromem Hi . Algoritmy pro operace MERGE, INSERT, MIN a DELETEMIN jsou zaloˇzeny na stejn´ ych idej´ıch jako algoritmy pro l´ınou implementaci v binomi´ aln´ıch hald´ ach, pouze poˇzadavek, aby strom byl izomorfn´ı s Hi , je nahrazen poˇzadavkem, ˇze m´ a rank i. Algoritmy pro

O(k+|H|)

16

operace DECREASE, INCREASE a DELETE vych´ azej´ı z algoritm˚ u pro tyto operace −1 3 v leftist haldách. V algoritmech pˇredpokl´ ad´ ame, ˇze c = log ( 2 ). MERGE(H1 , H2 ): ˇ konkatenaci seznam˚ Proved u H1 a H2 INSERT(x): Vytvoˇr haldu H1 reprezentuj´ıc´ı {x} MERGE(H, H1 ) MIN: Prohledej prvky reprezentované koˇreny vˇsech strom˚ uvH V´ ystup: nejmenˇs´ı z tˇechto prvk˚ u stromy rozdˇel do mnoˇzin Oi = {vˇ √sechny stromy v H s rankem i} vyvaz1({Oi | i = 0, 1, . . . , ⌊c log( 5|S| + 1)⌋}) DELETEMIN: Prohledej prvky reprezentované koˇreny vˇsech strom˚ uvH T := strom, jehoˇz koˇren reprezentuje nejmenˇs´ı prvek stromy rozdˇel do mnoˇzin Oi = {vˇsechny stromy v H s rankem i r˚ uzné od T } ∪ {podstrom T urˇcen´ y nˇekter´ ym synem koˇrene√T s rankem i} vyvaz1({Oi | i = 0, 1, . . . , ⌊c log( 5|S| + 1)⌋}) vyvaz1({Oi | i = 0, 1, . . . , k}): i := 0, H := ∅ while existuje Oi 6= ∅ do while |Oi | > 1 do vezmi dva r˚ uzné stromy T1 a T2 z Oi odstraˇ n je z Oi spoj(T1 , T2 ) vloˇz do Oi+1 enddo if Oi 6= ∅ then strom T ∈ Oi odstraˇ n z Oi a vloˇz ho do H endif i := i + 1 enddo V´ ystup: H spoj(T1 , T2 ): if f (koˇren T1 ) > f (koˇren T2 ) then vymˇen ˇ stromy T1 a T2 endif vytvoˇr nového syna v koˇrene T1 v :=koˇren T2

[Noví synové se ukládají na konec seznamu synů]

DECREASE(s, a): T :=strom v H, kter´ y obsahuje vrchol reprezentuj´ıc´ı s

17

v :=vrchol stromu T reprezentuj´ıc´ı s if v nen´ı koˇren then y vrcholem v odtrhni podstrom T ′ urˇcen´ vyvaz2(T, v) if v byl oznaˇcen then zruˇs oznaˇcen´ı v endif vloˇz T ′ do H endif f (v) := f (v) − a

[Zrušíme označení, protože v je nyní kořen T']

INCREASE(s, a): T :=strom v H, kter´ y obsahuje vrchol reprezentuj´ıc´ı s v :=vrchol stromu T reprezentuj´ıc´ı s if v nen´ı list then odtrhni podstrom T ′ urˇcen´ y vrcholem v if v nen´ı koˇren then vyvaz2(T, v) endif if v byl oznaˇcen then zruˇs oznaˇcen´ı v endif zruˇs oznaˇcen´ı vˇsech syn˚ u vrcholu v odtrhni podstromy T ′ urˇcené vˇsemi syny v a vloˇz je do H do H vloˇz strom maj´ıc´ı jen vrchol v endif f (v) := f (v) + a DELETE(s): T :=strom v H, kter´ y obsahuje vrchol reprezentuj´ıc´ı s v :=vrchol stromu T reprezentuj´ıc´ı s if v nen´ı list then zruˇs oznaˇcen´ı syn˚ u vrcholu v odtrhni podstromy urˇcené vˇsemi syny vrcholu v a vloˇz je do H endif if v nen´ı koˇren then vyvaz2(T, v) endif zruˇs vrchol v vyvaz2(T, v): u := otec v while u je oznaˇcen do u′ := otec(u), zruˇs oznaˇcen´ı u odtrhni podstrom T ′ urˇcen´ y vrcholem u ′ ′ vloˇz T do H, u := u enddo if u nen´ı koˇren T then oznaˇc u endif

[Stoupáme po označených vrcholech a odoznačujeme a odtrháváme podstromy a vkládáme je do haldy.] Vysvětlení operace vyvaz2 viz poslední řádka na této stránce.

Vˇsimnˇeme si, ˇze kdyˇz stromy T1 a T2 maj´ı rank i, pak procedura spoj(T1 , T2 ) vytvoˇr´ı strom s rankem i + 1. Aby algoritmy pro operace MIN a DELETEMIN byly korektn´ı, mus´ıme ukázat, ˇze √ vˇsechny stromy ve Fibonacciho haldˇe H reprezentuj´ıc´ı mnoˇzinu S maj´ı rank nejv´ yˇse c log( 5|S| + 1). Jen tak zajist´ıme, aby v´ ysledn´ a halda reprezentovala S, respektive S \ {prvek s nejmenˇs´ı hodnotou f }. Operace vyvaz1 zajiˇsˇtuje, ˇze od kaˇzdého vyvaz2

18

vrcholu stromu r˚ uzného od koˇrene byl v tomto stromˇe odtrˇzen podstrom nejv´ yˇse jednoho syna – v tom pˇr´ıpadˇe je tento prvek oznaˇcen a kdyˇz se mu odtrh´ av´ a podstrom dalˇs´ıho syna, bude odtrˇzen i cel´ y podstrom tohoto vrcholu (t´ım se tento vrchol stane koˇrenem stromu). Kdyˇz se pozdˇeji stane tento vrchol zase vrcholem r˚ uzn´ ym od koˇrene, cel´ y proces se opakuje. Sloˇ zitost operac´ı Naˇs´ım c´ılem bude odhadnout amortizovanou sloˇzitost tˇechto operac´ı, protoˇze sloˇzitost v nejhorˇs´ım pˇr´ıpadˇe nen´ı pouˇziteln´ y v´ ysledek. Abychom to mohli udˇelat, spoˇc´ıt´ ame parametry sloˇzitosti jednotliv´ ych operac´ı: MERGE – ˇcasová sloˇzitost O(1), nevznik´ a ˇz´ adn´ y nov´ y strom, oznaˇcené vrcholy se nemˇen´ı; INSERT – ˇcasová sloˇzitost O(1), pˇribyl jeden strom, oznaˇcené vrcholy se nemˇen´ı; MIN – ˇcasová sloˇzitost O(|H|), po proveden´ı operace r˚ uzné stromy v haldˇe maj´ı r˚ uzné ranky, oznaˇcené vrcholy se nemˇen´ı; DELETEMIN – ˇcasová sloˇzitost O(|H| + poˇcet syn˚ u v), kde v reprezentoval prvek s nejmenˇs´ı hodnotou f . Po proveden´ı operace r˚ uzné stromy v haldˇe maj´ı r˚ uzné ranky, ˇzádn´ y nov´ y vrchol nebyl oznaˇcen, nˇekteré oznaˇcené vrcholy pˇrestaly b´ yt oznaˇcené; DECREASE – ˇcasová sloˇzitost O(1+c), kde c je poˇcet vrchol˚ u, které pˇrestaly b´ yt oznaˇcené. Bylo pˇridáno 1 + c nov´ ych strom˚ u a byl oznaˇcen nejv´ yˇse jeden vrchol; INCREASE – ˇcasová sloˇzitost O(1 + c + d), kde c je poˇcet vrchol˚ u, které pˇrestaly b´ yt oznaˇcené, d je poˇcet syn˚ u vrcholu v reprezentuj´ıc´ıho prvek, jehoˇz hodnota se zvyˇsuje. Bylo pˇridáno nejv´ yˇse 1 + c + d nov´ ych strom˚ u a byl oznaˇcen nejv´ yˇse jeden vrchol; DELETE – ˇcasová sloˇzitost O(1+c+d), kde c je poˇcet vrchol˚ u, které pˇrestaly b´ yt oznaˇcené, d je poˇcet syn˚ u vrcholu v reprezentuj´ıc´ıho prvek, kter´ y se m´ a odstranit. Bylo pˇridáno nejv´ yˇse c + d nov´ ych strom˚ u a byl oznaˇcen nejv´ yˇse jeden vrchol. Ohodnocení konfigurace pro amort. složitost:

Pro v´ ypoˇcet amortizované sloˇzitosti mus´ıme nejprve navrhnout funkci ohodnocuj´ıc´ı konfigurace. Pˇri vyˇsetˇrován´ı l´ıné implementace binomi´ aln´ıch hald se uk´ azalo, ˇze vhodn´ ym ohodnocen´ım je poˇcet strom˚ u v haldˇe. Kdyˇz si ale prohlédneme algoritmus pro operaci DECREASE, vid´ıme, ˇze zde je vhodné br´ at do ohodnocen´ı i poˇcet oznaˇcen´ ych vrchol˚ u, a to dokonce tak, aby se pokryl nejen ˇcas, ale i pˇr´ır˚ ustek strom˚ u. To vede k n´ asleduj´ıc´ımu ohodnocen´ı konfigurace: ohodnocen´ı je poˇcet strom˚ u v konfiguraci plus dvojn´ asobek poˇctu (matematicky: #stromu + 2*#pocet_oznacenych_vrcholu : ) ) oznaˇcen´ ych vrchol˚ u. Nechˇt ρ(n) je maximáln´ı poˇcet syn˚ u vrcholu ve Fibonacciho haldˇe reprezentuj´ıc´ı n-prvkovou mnoˇzinu. Pak amortizovaná sloˇzitost operac´ı MERGE, INSERT a DECREASE je O(1) a operac´ı MIN, DELETEMIN, INCREASE a DELETE je O(ρ(n)).

DEF:

Abychom spoˇc´ıtali odhad ρ(n), vyuˇzijeme toho, ˇze Fibonacciho halda vznikla z prázdné haldy pomoc´ı popsan´ ych algoritm˚ u. Nejprve uvedeme jedno technické lemma. v

u

Lemma. Nechˇt v je vrchol stromu ve Fibonacciho haldˇe a nechˇt u je i-t´ y nejstarˇs´ı syn vrcholu v. Pak u m´ a aspoˇ n i − 2 syn˚ u. D˚ ukaz. V momentˇe, kdy se u stával synem v, se aplikovala operace spoj, u a v byly koˇreny strom˚ u a mˇely stejn´ y poˇcet syn˚ u. Podle pˇredpoklad˚ u mˇel vrchol v alespoˇ n i − 1 syn˚ u (jinak by u nebyl i-t´ y nejstarˇs´ı syn), a protoˇze se od u mohl odtrhnout jen jeden syn, dostáváme, ˇze u mus´ı m´ıt alespoˇ n i − 2 syn˚ u.

19

v má k synů

v

listy

Tvrzen´ı. Nechˇt v je vrchol stromu ve Fibonacciho haldˇe, kter´ y m´ a pr´ avˇe i syn˚ u. Pak u. podstrom urˇcen´ y vrcholem v m´ a aspoˇ n Fi+2 vrchol˚ D˚ ukaz. Tvrzen´ı dokáˇzeme indukc´ı podle maxim´ aln´ı délky cesty z vrcholu v do nˇekterého listu. Tato délka je 0, právˇe kdyˇz v je list. V tom pˇr´ıpadˇe v nem´ a syna a podstrom urˇcen´ y vrcholem v má jedin´ y vrchol. Protoˇze 1 = F2 = F0+2 , tvrzen´ı plat´ı. Mˇejme nyn´ı vrchol v, kter´ y má k syn˚ u, a nechˇt maximáln´ı délka cesty z vrcholu v do list˚ u je j. Pˇredpokládejme, ˇze tvrzen´ı plat´ı pro vˇsechny vrcholy, pro nˇeˇz tato délka je menˇs´ı neˇz j, tedy plat´ı i pro vˇsechny syny vrcholu v. Pak pro i > 1 m´ a i-t´ y nejstarˇs´ı syn vrcholu v podle pˇredchoz´ıho lemmatu alespoˇ n i − 2 syn˚ u a podle indukˇcn´ıho pˇredpokladu podstrom urˇcen´ y t´ımto synem má alespoˇ n Fi vrchol˚ u. Odtud dost´ av´ ame, ˇze podstrom urˇcen´ y vrcholem v m´ a alespoˇ n 1 + F2 +

délka cesty je j

k X

Fi = 1 +

i=2

k X

Fi

i=1

vrchol˚ u, protoˇze F1 = F2 (na levé stranˇe prvn´ı 1 je za vrchol v a prvn´ı F2 je za nejstarˇs´ı vrchol). Indukc´ı pak dostaneme, ˇze 1+

n X

Fi = Fn+2

i=1

pro vˇsechna n ≥ 0. Skuteˇcnˇe, pro n = 0 plat´ı 1+

0 X

Fi = 1 = F2 = F0+2 ,

i=1

pro n = 1 máme 1+

1 X

Fi = 1 + F1 = 2 = F3 = F1+2

i=1

a z indukˇcn´ıho pˇredpokladu a z vlastnost´ı Fibonacciho ˇc´ısel plyne, ˇze 1+

n X

Fi = 1 +

i=1

n−1 X

Fi + Fn = Fn+1 + Fn = Fn+2 .

i=1

Kdyˇz shrneme tato fakta, dostáv´ ame, ˇze podstrom urˇcen´ y vrcholem v m´ a alespoˇ n Fi+2 vrchol˚ u, a tvrzen´ı je dokázáno. Vezmˇeme nyn´ı nejmenˇs´ı i takové, ˇze n < Fi . Protoˇze posloupnost {Fi }∞ ı, plyne i=1 je rostouc´ z pˇredchoz´ıho tvrzen´ı, ˇze kaˇzd´ y vrchol ve Fibonacciho haldˇe reprezentuj´ıc´ı n−prvkovou mnoˇzinu má ménˇe neˇz i − 2 syn˚ u (kdyˇz vrchol v Fibonacciho haldy m´ a i − 2 syn˚ u, pak podstrom vrcholu v reprezentuje mnoˇzinu alespoˇ n s Fi prvky). Proto ρ(n) < i − 2. K odhadu velikosti i pouˇzijeme explicitn´ı vzorec pro i-té Fibonacciho ˇc´ıslo: Fi =

√ 1+ 5 i 2

− √ 5

√ 1− 5 i 2

√ √ 1 1 + 5 i 1 1 − 5 i =√ −√ . 2 2 5 5

20 √

Protoˇze 0 > 1−2 5 > − 34 a protoˇze i = 1, 2, . . . , a tedy

√

5 > 2, dost´ av´ ame, ˇze | √15

√ 1− 5 i | 2

<

3 8

pro vˇsechna

√

5 a zlogarit-

√ √ 1 1 + 5 i 3 1 1 + 5 i 3 √ − < Fi < √ + . 2 8 2 8 5 5 Odtud plyne, ˇze kdyˇz i splˇ nuje √ 1 1 + 5 i 3 n≤ √ − , 2 8 5 pak n < Fi . Pˇreveden´ım 38 na druhou stranu v´ yrazu, jeho vyn´ asoben´ım mován´ım dostaneme následuj´ıc´ı ekvivalenci: (#1)

Z

√ 3 5 8

√ √ 1 + 5 3 5 log2 ( 5n + ) ≤ i log2 8 2 √

<1az

3 2

<

√ 1+ 5 2

√ 1 1 + 5 i 3 n≤ √ − . 2 8 5

⇔

plyne, ˇze √ log2 ( 5n +

√ 3 5 8 ) √ log2 1+2 5

√ log2 ( 5n + 1) < . log2 32

Tedy plat´ı následuj´ıc´ı implikace √ log2 ( 5n + 1)
√ log2 ( 5n+1) log2 3−1

=⇒

√ log2 ( 5n +

√ 3 5 8 ) √ 1+ 5 2

log2

< i.

< i, pak n < Fi , a tedy ρ(n) < i − 2.

V´ ysledky shrneme do následuj´ıc´ı vˇety: Vˇ eta. Ve Fibonacciho haldˇe, kter´ a reprezentuje n-prvkovou mnoˇzinu, m´ a kaˇzd´ y vrchol stupeˇ n menˇs´ı neˇz √ log2 ( 5n + 1) − 2. (log2 3) − 1 Amortizovan´ a sloˇzitost operac´ı INSERT, MERGE a DECREASE je O(1) a amortizovan´ a sloˇzitost operac´ı MIN, DELETEMIN, INCREASE a DELETE je O(log n). Operace MIN a DELETEMIN jsou korektn´ı. Pro u ´plnost dokáˇzeme, ˇze Fi = Pro i = 1 plat´ı √ 1+ 5 1 2

− √ 5

√ 1+ 5 2

√ 1− 5 1 2

i

=

− √ 5

√ 1− 5 2

1+

√

i

.

5−1+ √ 2 5

√

5

√ 2 5 = √ = 1 = F1 . 2 5

21

Pro i = 2 plat´ı √ 1+ 5 2 2

− √ 5

√ 1− 5 2 2

√ √ √ 1+2 5+5−1+2 5−5 4 5 √ = = √ = 1 = F2 . 4 5 4 5

Indukˇcn´ı krok: √ 1+ 5 i 2

− √ 5

√ 1− 5 i 2

=

√ √ 1+ 5 i−2 1+ 5 2 2 2

√ √ 1+ 5 i−2 3+ 5 2 2

− √ 5

√ √ 1− 5 i−2 1− 5 2 2 2

=

√ √ i−2 3− 5 − 1−2 5 2 √ = 5 √ √ √ √ 1+ 5 i−2 1+ 5 1− 5 i−2 1− 5 1 + − 1 + 2 2 2 2 √ = 5 √ √ √ √ 1+ 5 i−2 1+ 5 i−1 1− 5 i−2 1− 5 i−1 + − − 2 2 2 2 √ = 5 √ √ √ √ 1+ 5 i−2 1− 5 i−2 1+ 5 i−1 1− 5 i−1 − − 2 2 2 2 √ √ + = Fi−2 + Fi−1 = Fi . 5 5

Tedy indukc´ı dostáváme poˇzadovan´ y vztah. Aplikace Vrát´ıme se k Dijkstrovˇe algoritmu. Mnoˇzinu U budeme reprezentovat pomoc´ı Fibonacciho haldy. Protoˇze ohodnocen´ı je nezáporné a ohodnocen´ı poˇc´ ateˇcn´ı haldy je 0, dává odhad amortizované sloˇzitosti také odhad ˇcasové sloˇzitosti (viz odstavec IV.). Proto Dijkstr˚ uv algoritmus s pouˇzit´ım Fibonacciho haldy vyˇzaduje v nejhorˇs´ım pˇr´ıpadˇe ˇcas O(|X|(1+log |X|)+ |R|) = O(|R| + |X| log |X|). Stejn´ y v´ ysledek dostaneme i pro konstrukci nejmenˇs´ı napnuté kostry grafu. Kdy použít Fib. a kdy d reg. haldu:

Otázka je, kdy v Dijkstrovˇe algoritmu nebo v algoritmu konstruuj´ıc´ım nejmenˇs´ı napnutou kostru pouˇz´ıt Fibonacciho haldu a kdy napˇr. d-regul´ arn´ı haldy. Lze ˇr´ıci, ˇze Fibonacciho halda by mˇela b´ yt v´ yraznˇe lepˇs´ı pro vˇetˇs´ı, ale ˇr´ıdké grafy (tj. grafy s mal´ ym poˇctem hran). Dá se pˇredpokládat, ˇze d-regulárn´ı haldy budou lepˇs´ı (d´ıky sv´ ym jednoduˇsˇs´ım algoritm˚ um) pro husté grafy (tj. grafy, kde poˇcet hran je |X|1+ε pro vhodné ε > 0). Problém je, pro které hodnoty nastává zlom. Nev´ım o ˇz´ adn´ ych experiment´ aln´ıch ani teoretick´ ych v´ ysledc´ıch tohoto typu. ´ pr ˇehled Historicky Binárn´ı neboli 2-regulárn´ı haldy zavedl Williams 1964. Jejich zobecnˇen´ı na d-regulárn´ı haldy pocház´ı od Johnsona 1975. Leftist haldy definoval Crane 1972 a detailnˇe popsal Knuth 1975. Binomiáln´ı haldy navrhnl Vuillemin 1978, Brown 1978 je implementoval a prokázal jejich praktickou pouˇzitelnost. Fibonacciho haldy byly zavedeny Fredmanem a Tarjanem 1987.

22

VII. Tˇr´ıdic´ı algoritmy Jednou z nejˇcastˇeji ˇreˇsen´ ych u ´loh pˇri pr´ aci s daty je setˇr´ıdˇen´ı posloupnosti prvk˚ u nˇejakého typu. Proto velká pozornost byla a je vˇenov´ ana tˇr´ıdic´ım algoritm˚ um ˇreˇs´ıc´ım tuto u ´lohu, která sv´ ym charakterem a sv´ ymi poˇzadavky na algoritmy je ˇrazena do datov´ ych struktur. Byla navrˇzena ˇrada algoritm˚ u, které se st´ ale jeˇstˇe analyzuj´ı a optimalizuj´ı. Anal´ yzy jsou velmi detailn´ı a algoritmy se studuj´ı za r˚ uzn´ ych vstupn´ıch pˇredpoklad˚ u. Kromˇe toho tˇr´ıdˇen´ı je jedna z mála u ´loh, pro kterou alespoˇ n za jist´ ych pˇredpoklad˚ u um´ıme spoˇc´ıtat doln´ı odhad sloˇzitosti. Def:

Formulace u ´lohy: Nechˇt U je totálnˇe uspoˇrádané univerzum. u z univerza U . Vstup: Prostá posloupnost {a1 , a2 , . . . , an } prvk˚ V´ ystup: Rostouc´ı posloupnost {b1 , b2 , . . . , bn } takov´ a, ˇze {ai | i = 1, 2, . . . , n} = {bi | i = 1, 2, . . . , n}. Tento problém se naz´ yvá tˇr´ıdˇen´ı. V praxi se setk´ av´ ame s ˇradou jeho modifikac´ı, a nichˇz asi nejbˇeˇznˇejˇs´ı je vynechán´ı pˇredpokladu, ˇze vstupem je prost´ a posloupnost. Pak jsou dvˇe variˇ anty ˇreˇsen´ı – bud se ve v´ ystupn´ı posloupnosti odstran´ı duplicity nebo v´ ystupn´ı posloupnost zachová ˇcetnost prvk˚ u ze vstupn´ı posloupnosti. Základn´ı algoritmy, které ˇreˇs´ı tˇr´ıdic´ı problém, jsou QUICKSORT, MERGESORT a HEAPSORT. HEAPSORT S algoritmem HEAPSORT jsme se sezn´ amili pˇri aplikac´ıch hald. Byl to prvn´ı algoritmus pouˇz´ıvaj´ıc´ı haldy (binárn´ı regul´ arn´ı haldy byly definov´ any pr´ avˇe pˇri n´ avrhu HEAPSORTU). Pod´ıváme se detailnˇeji na jednu z jeho implementac´ı, kter´ a tˇr´ıd´ı takzvanˇe na m´ıstˇe.

Požadavky na třídění:

Duální podmínka uspořádání (chceme MAXHEAP):

Pozn.:

Tˇr´ıdic´ı algoritmy se ˇcasto pouˇz´ıvaj´ı jako podprocedura pˇri ˇreˇsen´ı jin´ ych u ´loh. V takovém pˇr´ıpadˇe je obvykle vstupn´ı posloupnost uloˇzena v poli v pracovn´ı pamˇeti programu a poˇzadavkem je setˇr´ıdit ji bez pouˇzit´ı dalˇs´ı pamˇeti pouze s v´ yjimkou omezeného (malého) poˇctu pomocn´ ych promˇenn´ ych. Pro ˇreˇsen´ı tohoto problému se hod´ı HEAPSORT. Zvol´ıme implementaci HEAPSORTU pomoc´ı d-regul´ arn´ıch hald, které jsou reprezentovány polem, v nˇemˇz je uloˇzena vstupn´ı posloupnost (viz odstavec Aplikace v kapitole o d-regulárn´ıch haldách). Pouˇzijeme algoritmus s jedinou zmˇenou – budeme poˇzadovat du´ aln´ı podm´ınku na uspoˇrádán´ı (to znamená, ˇze prvek reprezentovan´ y vrcholem bude menˇs´ı neˇz prvek reprezentovan´ y jeho otcem) a nahrad´ıme operace MIN a DELETEMIN operacemi MAX a DELETEMAX. V algoritmu vˇzdy um´ıst´ıme odebrané maximum na m´ısto prvku v posledn´ım listu haldy (tj. prvku, kter´ y ho pˇri operaci DELETEMAX nahradil) m´ısto toho, abychom ho vloˇzili do v´ ystupn´ı posloupnosti. Mus´ıme si ale pamatovat, kde v poli konˇc´ı reprezentovaná halda. Kaˇzdá aplikace operace DELETEMAX zkr´ at´ı poˇc´ ateˇcn´ı u ´sek pole reprezentuj´ıc´ıho haldu o jedno m´ısto a z´ aroveˇ n o toto m´ısto zvˇetˇs´ı druhou ˇc´ ast, ve které je uloˇzena jiˇz setˇr´ıdˇená ˇcást posloupnosti. HEAPSORTU je stále vˇenována velk´ a pozornost a bylo navrˇzeno nˇekolik jeho modifikac´ı, snaˇz´ıc´ıch se napˇr. minimalizovat poˇcet porovn´ an´ı prvk˚ u apod.

23

MERGESORT Nejstarˇs´ı z uveden´ ych algoritm˚ u je MERGESORT, kter´ y je starˇs´ı neˇz je poˇc´ıtaˇcová éra, neboˇt nˇekteré jeho verze se pouˇz´ıvaly uˇz pˇri mechanickém tˇr´ıdˇen´ı. Pop´ıˇseme jednu jeho iteraˇcn´ı verzi, tzv. pˇrirozen´ y MERGESORT. MERGESORT(a1 , a2 , . . . , an ): Q je prázdná fronta, i = 1 while i ≤ n do j := i while i < n a ai+1 > ai do i := i + 1 enddo posloupnost P = (aj , aj+1 , . . . , ai ) vloˇz do Q i := i + 1 enddo while |Q| > 1 do vezmi P1 a P2 dvˇe posloupnosti z vrcholu Q odstraˇ n P1 a P2 z Q MERGE(P1 , P2 ) vloˇz na konec Q enddo V´ ystup: posloupnost z Q

Sliji dvě neklesající PSP do PSP c_k:

Korektnost:

Složitost procedury MERGE:

Hledám vždy setříděný úsek posloupnosti a_i Čas: O(n)

Slívám po dvou posloupnostech z Q dokud nejsem slitý na jedinou setříděnou PSP

MERGE(P1 = (a1 , a2 , . . . , an ), P2 = (b1 , b2 , . . . , bm )): P := je prázdná posloupnost, i := 1, j := 1, k := 1 while i ≤ n a j ≤ m do if ai < bj then Stacilo dat jednou za endif. ck := ai , i := i + 1, k := k + 1 else ck := bj , j := j + 1, k := k + 1 endif enddo Posloupnost a_i může být delší než PSP while i ≤ n do ck := ai , i := i + 1, k := k + 1 enddo Posloupnost b_i může být delší než PSP while j ≤ m do ck := bj , j := j + 1, k := k + 1 enddo V´ ystup: P = (c1 , c2 , . . . , cn+m )

b_i

a_i

Vˇsimnˇeme si, ˇze vˇsechny posloupnosti v Q jsou rostouc´ı a ˇze sjednocen´ım vˇsech jejich prvk˚ u je vˇzdy na zaˇcátku bˇehu cyklu while |Q| > 1 do mnoˇzina {ai | i = 1, 2, . . . , n}. Protoˇze poˇcet posloupnost´ı ve frontˇe Q je nejv´ yˇse roven délce vstupn´ı posloupnosti a kaˇzd´ y pr˚ ubˇeh tohoto cyklu zmenˇs´ı jejich poˇcet o 1, je algoritmus MERGESORT korektn´ı. Spoˇc´ıtáme ˇcasovou sloˇzitost MERGESORTU. Nejprve vyˇsetˇr´ıme sloˇzitost podprocedury MERGE. Protoˇze urˇcen´ı prvku ck vyˇzaduje ˇcas O(1) (provede se nejv´ yˇse jedno porovnán´ı) a protoˇze maximáln´ı hodnota k je n + m, dost´ av´ ame, ˇze podprocedura MERGE vyˇzaduje ˇcas O(n + m) (nejv´ yˇse n + m porovn´ an´ı), kde n a m jsou délky vstupn´ıch posloupnost´ı.

24 Složitost procedury MERGESORT:

Nyn´ı vypoˇcteme sloˇzitost hlavn´ı procedury. Zˇrejmˇe prvn´ı cyklus vyˇzaduje lineárn´ı ˇcas. Vyˇsetˇr´ıme druh´ y cyklus prob´ıhaj´ıc´ı pˇres frontu Q. Pˇredpokl´ adejme, ˇze pˇred prvn´ım bˇehem tohoto cyklu je na vrcholu Q speci´ aln´ı znak ♮, kter´ y se vˇzdy pouze pˇrenese z vrcholu Q na jej´ı konec. Protoˇze mezi dvˇema pˇrenosy ♮ projde kaˇzd´ y prvek vstupn´ı posloupnosti podprocedurou MERGE právˇe jednou, vyˇzaduj´ı jednotlivé bˇehy cyklu ˇcas O(n), kde n je délka vstupn´ı posloupnosti (a zároveˇ n souˇcet vˇsech délek posloupnost´ı v Q). Vˇsechny posloupnosti v Q maj´ı na poˇcátku délku ≥ 1. Odtud jednoduchou indukc´ı dostaneme, ˇze po i-tém pˇrenosu znaku ♮ maj´ı délku ≥ 2i−1 . Proto poˇcet pˇrenos˚ u je nejv´ yˇse ⌈log2 n⌉, a tedy algoritmus MERGESORT vyˇzaduje ˇcas O(n log n) (provede se nejv´ yˇse n log n porovnán´ı). Vzhledem k poˇctu porovnán´ı je MERGESORT optim´ aln´ı tˇr´ıdic´ı algoritmus. Nav´ıc v této verzi je adaptivn´ı na pˇredtˇr´ıdˇené posloupnosti, které maj´ı jen mal´ y poˇcet dlouh´ ych setˇr´ıdˇen´ ych u ´sek˚ u (bˇeh˚ u). Pˇri konstantn´ım poˇctu bˇeh˚ u m´ a sloˇzitost O(n). Jin´ a jeho verze, která zaˇc´ıná sléván´ı vˇzdy od jednoprvkov´ ych posloupnost´ı (tzv. pˇr´ım´ y MERGESORT) tuto vlastnost nemá. QUICKSORT Nyn´ı pop´ıˇseme patrnˇe v˚ ubec nejpouˇz´ıvanˇejˇs´ı tˇr´ıdic´ı algoritmus, kter´ ym je QUICKSORT. D˚ uvodem je, ˇze pro obecnou posloupnost je nejrychlejˇs´ı, pˇri rovnomˇerném rozloˇzen´ı vstupn´ıch polsoupnost´ı má nejmenˇs´ı oˇcek´ avan´ y ˇcas. Quick(ai , ai+1 , . . . , aj ): if i = j then [Indexy i a j máme ze vstupu algoritmu] V´ ystup: (ai ) else zvol k takové, ˇze i ≤ k ≤ j, a := ak , vymˇen ˇ ai a ak , l := i + 1, q := j (#3)while true do pivot (#1)while al < a do l := l + 1 enddo [Hledám prvky menší než pivot od začátku PSP a_i] (#2)while aq > a do q := q − 1 enddo [Hledám prvky větší než pivot od konce PSP a_i] Příklad: if l ≥ q then =============================== 1 2 6 4 5 7 3 8 9 exit [break while cyclus] i k j else PSP je upravena před #1 takto: vymˇen ˇ al a aq , l := l + 1, q := q − 1 endif 5 2 6 4 1 7 3 8 9 i l q=j enddo if i + 1 = l then Po #2 PSP vypadají indexy takto: V´ ystup(a,Quick(aq+1, aq+2 , . . . , aj )) 5 2 6 4 1 7 3 8 9 else i l q j if j = q then Po skončení while cyklu #3: V´ ystup(Quick(ai+1 , ai+2 , . . . , al−1 ), a) 5 2 3 4 1 7 6 8 9 else i q l j V´ ystup(Quick(ai+1 , ai+2 , . . . , al−1 ), a,Quick(aq+1, . . . , aj )) endif endif endif

25

QUICKSORT(a1 , a2 , . . . , an ): V´ ystup(Quick(a1 , a2 , . . . , an )) Korektnost algoritmu:

Algoritmus Quick setˇr´ıd´ı posloupnost (ai , ai+1 , . . . , aj ) tak, ˇze pro prvek a = ak vytvoˇr´ı posloupnost (ai , ai+1 , . . . , al−1 ) vˇsech prvk˚ u menˇs´ıch neˇz a a posloupnost (aq+1 , . . . , aj ) vˇsech prvk˚ u vˇetˇs´ıch neˇz a. Na tyto posloupnosti pak zavol´ a s´ am sebe a do v´ ysledné posloupnosti uloˇz´ı nejprve setˇr´ıdˇenou prvn´ı posloupnost, pak prvek a a nakonec setˇr´ıdˇenou druhou posloupnost. Korektnost procedury Quick i algoritmu QUICKSORT je tedy zˇrejmá, protoˇze l ≤ j a i ≤ q.

Procedura Quick bez rekurzivn´ıho vol´ an´ı vyˇzaduje ˇcas O(j − i). Tedy kdyby ak byl medián (tj. prostˇredn´ı prvek) posloupnosti (ai , ai+1 , . . . , aj ), pak by algoritmus QUICKSORT v nejhorˇs´ım pˇr´ıpadˇe vyˇzadoval ˇcas O(n log n). Jak uvid´ıme pozdˇeji, medi´ an lze sice nalézt v lineárn´ım ˇcase, ale pouˇzit´ı jakékoli procedury pro jeho nalezen´ı m´ a za n´ asledek, ˇze algoritmy MERGESORT a HEAPSORT budou rychlejˇs´ı (nikoliv asymptoticky, ale multiplikativn´ı konstanta bude v tomto pˇr´ıpadˇe vysok´ a). Proto je tˇreba vybrat prvek ak (tzv. pivot) co Původní nejrychleji. P˚ uvodnˇe se bral prvn´ı nebo posledn´ı prvek posloupnosti. Pˇri této volbˇe a pˇri (historicky) erném rozdˇelen´ı vstup˚ u je oˇcek´ avan´ y ˇcas QUICKSORTU O(n log n) a algoritmus výběr pivota: rovnomˇ je obvykle rychlejˇs´ı neˇz MERGESORT a HEAPSORT. Avˇsak ˇcas v nejhorˇs´ım pˇr´ıpadˇe je kvadratick´ y a dokonce pro urˇcitá rozdˇelen´ı vstupn´ıch dat je i oˇcek´ avan´ y ˇcas kvadratick´ y. Proto tuto volbu pivota nen´ı vhodné pouˇz´ıvat pro u ´lohy, kdy nezn´ ame rozdˇelen´ı vstupn´ıch dat (mohlo by se stát, ˇze je nevhodné). Jednoduˇse to lze napravit tak, ˇze budeme volit k Náhodný pivot: n´ ahodnˇe. Bohuˇzel pouˇzit´ı pseudon´ ahodného gener´ atoru také vyˇzaduje jist´ y ˇcas, a pak uˇz by algoritmus zase nemusel b´ yt rychlejˇs´ı neˇz algoritmy MERGESORT a HEAPSORT (nav´ıc takto náhodnˇe zvolen´ y prvek nen´ı skuteˇcnˇe n´ ahodn´ y, ale to v tomto pˇr´ıpadˇe nevad´ı). Nejlepší výběr D˚ usledkem je návrh vyb´ırat pivota jako medi´ an ze tˇr´ı nebo pˇeti pevnˇe zvolen´ ych prvk˚ u pivota: posloupnosti. Praxe ukázala, ˇze tento v´ ybˇer pivota je nejpraktiˇctˇejˇs´ı, d´ a se provést rychle a zajiˇsˇtuje dostateˇcnou náhodnost. Protoˇze pˇri kaˇzdém volán´ı má Quick jako argument kratˇs´ı vstupn´ı posloupnost, lze ukázat, ˇze: (1) pˇri kaˇzdé volbˇe pivota je nejhorˇs´ı ˇcas algoritmu QUICKSORT O(n2 ), (2) pokud je pivot vybrán jednoduch´ ym a rychl´ ym zp˚ usobem (to plat´ı, i kdyˇz se vol´ı náhodnˇe), pak existuj´ı vstupn´ı posloupnosti, které vyˇzaduj´ı ˇcas O(n2 ), (3) oˇcekávan´ y ˇcas je O(n log n). Předpoklady následující analýzy:

Následná anal´ yza oˇcekávaného pˇr´ıpadu je pro n´ ahodnˇe zvoleného pivota (bez dalˇs´ıho pˇredpokladu na vstupn´ı data) nebo pro pˇr´ıpad, kdy pivot je pevnˇe zvolen a data jsou rovnomˇernˇe rozdˇelena. výpočtu

Ukáˇzeme dva zp˚ usoby v´ ypoˇcty oˇcekávaného ˇcasu. Jeden je zaloˇzen na nˇekolika jednoduch´ ych pozorován´ıch a nen´ı v nˇem mnoho poˇc´ıt´ an´ı, druh´ y na rekurzivn´ım v´ ypoˇctu. Ten je poˇcetnˇe nároˇcnˇejˇs´ı, ale postup je standardn´ı. Hlavn´ı idea v obou pˇr´ıpadech spoˇc´ıv´ a v tom, ˇze oˇcekávan´ y ˇcas algoritmu QUICKSORT je u ´mˇern´ y oˇcek´ avanému poˇctu porovnán´ı v algoritmu QUICKSORT. Tento fakt plyne pˇr´ımo z popisu algoritmu. Budeme tedy poˇc´ıtat oˇcekávan´ y poˇcet porovnán´ı pro algoritmus QUICKSORT. Prvn´ı zp˚ usob v´ ypoˇctu: Kaˇzdé dva prvky ai a aj algoritmus QUICKSORT porovn´ a pˇri tˇr´ıdˇen´ı posloupnosti

26

(a1 , a2 , . . . , an ) nejv´ yˇse jednou, pˇriˇcemˇz kdyˇz porovn´ av´ a ai a aj , pak pro nˇejak´ y bˇeh podprocedury Quick je ai nebo aj pivot, ale v pˇredchoz´ıch bˇez´ıch Quick ai ani aj nebyl pivotem (protoˇze pivot je vˇzdy vyˇrazen z n´ asleduj´ıc´ıch vol´ an´ı této podprocedury). Náhodná proměnná X_i,j:

Nechˇt (b1 , b2 , . . . , bn ) je v´ ysledná posloupnost. Oznaˇcme Xi,j boolskou promˇenou, která má hodnotu 1, kdyˇz QUICKSORT provedl porovn´ an´ı mezi prvky bi a bj , a jinak má hodnotu 0. Pˇredpokládejme, ˇze je to náhodn´ a veliˇcina. Kdyˇz pi,j je pravdˇepodobnost, ˇze Xi,j = 1, pak oˇcekávaná hodnota Xi,j je E(Xi,j ) = 0(1 − pi,j ) + 1pi,j = pi,j . Protoˇze poˇcet porovnán´ı pˇri bˇehu algoritmu QUICKSORT je n n X X

Xi,j

[Počet všech porovnání]

i=1 j=i+1

a protoˇze oˇcekávaná hodnota souˇctu n´ ahodn´ ych promˇenn´ ych je souˇctem oˇcek´ avan´ ych hodnot, dostáváme, ˇze oˇcekávan´ y poˇcet porovn´ an´ı v algoritmu QUICKSORT je n n X X

E(Xi,j ) =

i=1 j=i+1

Výpočet p_{i,j}: Def strom výpočtu:

n n X X

pi,j .

[Očekávaný počet všech porovnání]

i=1 j=i+1

Abychom spoˇc´ıtali pi,j , pop´ıˇseme chov´ an´ı algoritmu QUICKSORT pomoc´ı modifikace stromu v´ ypoˇctu. Bude to binárn´ı strom, v nˇemˇz kaˇzd´ y vrchol odpov´ıd´ a jednomu bˇehu podprocedury Quick. Vrchol v bude vnitˇrn´ım vrcholem, kdyˇz odpov´ıdaj´ıc´ı podprocedura volila pivota, a tento pivot bude ohodnocen´ım v. V podstromu levého syna vrcholu v budou právˇe vˇsechna následuj´ıc´ı rekurzivn´ı volán´ı podprocedury Quick nad ˇc´ ast´ı posloupnosti, která pˇredcház´ı pivotu. Analogicky v podstromu pravého syna vrcholu v budou pr´ avˇe vˇsechna následuj´ıc´ı rekurzivn´ı volán´ı procedury Quick nad ˇc´ ast´ı posloupnosti, kter´ a následuje po pivotu. Listy stromu odpov´ıdaj´ı vol´ an´ı procedury Quick nad jednoprvkov´ ymi posloupnostmi a kaˇzd´ y takov´ y jednotliv´ y prvek ohodnocuje pˇr´ısluˇsn´ y list. Kdyˇz vrchol v odpov´ıdá volán´ı Quick nad posloupnost´ı (ai , ai+1 , . . . , aj ), pak vrcholy v podstromu levého syna v jsou ohodnoceny prvky z posloupnosti (ai , ai+1 , . . . , al−1 ) a vrcholy v podstromu pravého syna vrcholu v jsou ohodnoceny prvky z posloupnosti (aq+1 , . . . , aj ) (po pˇrerovnán´ı). Dále plat´ı {al | i ≤ l ≤ j} = {bl | i ≤ l ≤ j}. Oˇc´ıslujeme vrcholy tohoto stromu prohled´ av´ an´ım do ˇs´ıˇrky za pˇredpokladu, ˇze lev´ y syn ˇ vrcholu pˇredcház´ı pravému synu. Necht (c1 , c2 , . . . , cn ) je posloupnost prvk˚ u {ai | 1 ≤ i ≤ n} v poˇrad´ı daném t´ımto oˇc´ıslován´ım. Pak plat´ı, ˇze Xi,j = 1, pr´ avˇe kdyˇz prvn´ı prvek v ˇ bi nebo bj . Pravdˇepodobnost posloupnosti (c1 , c2 , . . . , cn ) z mnoˇziny {bl | i ≤ l ≤ j} je bud 2 2 tohoto jevu je j−i+1 , tedy pi,j = j−i+1 pro 1 ≤ i < j ≤ n. Odtud oˇcek´ avan´ y poˇcet porovnán´ı v algoritmu QUICKSORT je n n X X

i=1 j=i+1

pi,j =

n n X X

i=1 j=i+1

Z n n n−i+1 n X X 2 X 2 1 1 = ≤ 2n( ) ≤ 2n dx = 2n ln n. j −i+1 k k 1 x i=1

k=2

k=2

27

Druh´ y zp˚ usob v´ ypoˇctu: Oznaˇcme QS(n) oˇcekávan´ y poˇcet porovn´ an´ı proveden´ ych algoritmem QUICKSORT pˇri tˇr´ıdˇen´ı n-ˇclenné posloupnosti. Pak plat´ı QS(0) = QS(1) = 0 a n−1 n−1 1 X 2 X n − 1 + QS(k) + QS(n − k − 1) = n − 1 + ( QS(k)). QS(n) = n n

Z toho dostáváme,

k=0 k=0 Všechny možné volby pivota. S pivotem vždy porovnám všechny zbývající prvky kromě (tedy n 1 prvků) a musím započítat počet testů, které se provedou na "levé" a ˇze sebe na "pravé" PSP (původní PSP je rozdělena přes pivota na "levou" a "pravou"). n−1 X

nQS(n) = n(n − 1) + 2

QS(k).

[Vynásobili jsme obě strany rovnice proměnnou n]

k=0

Pˇrep´ıˇseme jeˇstˇe jednou tuto rovnici s n + 1 m´ısto n: (n + 1)QS(n + 1) = (n + 1)n + 2

n X

QS(k).

k=0

Od této rovnice odeˇcteme rovnici pˇredchoz´ı a po jednoduché u ´pravˇe z´ısk´ ame rekurentn´ı vztah 2n n+2 + QS(n). QS(n + 1) = n+1 n+1 Postupn´ ym dosazován´ım dostaneme ˇreˇsen´ı <= 1

n X n + 1 2(i − 1)

n X

n+1 X 1 1 QS(n) = ≤ 2(n + 1) = 2(n + 1) = i+1 i i+1 i i=2 i=2 i=3 Z n+1 n+1 X 1 1 1 1 2(n + 1) − ≤ 2(n + 1) ( dx) − = i 2 x 2 i=1 i=2 ln(n+1)

2n ln(n + 1) + 2 ln(n + 1) − n − 1. Pro dostateˇcnˇe velká n tedy plat´ı 2n ln(n + 1) + 2 ln(n + 1) − n ≤ 2n ln n. ń´ı tr ˇ´ıdic´ıch algoritm˚ Porovna u

Selection sort:

Nyn´ı porovnáme sloˇzitost algoritm˚ u HEAPSORT, MERGESORT, QUICKSORT, Asort (byl popsán v kapitole o (a, b)−stromech), SELECTIONSORT a INSERTIONSORT. Pˇripomeˇ nme si, ˇze SELECTIONSORT tˇr´ıd´ı posloupnost tak, ˇze jedn´ım pr˚ uchodem nalezne jej´ı nejmenˇs´ı prvek, kter´ y vyˇrad´ı a vloˇz´ı do v´ ysledné posloupnosti (ve verzi, která tˇr´ıd´ı na m´ıstˇe, ho vymˇen´ı s lev´ ym krajn´ım prvkem pole). Tento proces pak opakuje se zbytkem p˚ uvodn´ı posloupnosti. Tato idea byla z´ akladem algoritmu HEAPSORT. INSERTIONSORT tˇr´ıd´ı tak, ˇze do jiˇz setˇr´ıdˇeného zaˇc´ atku posloupnosti vkl´ ad´ a dalˇs´ı prvek,

28

kter´ y pomoc´ı v´ ymˇen zaˇrad´ı na správné m´ısto, a tento proces (zaˇc´ın´ a druh´ ym prvkem zleva) opakuje. Výsledky pro model RAM:

QUICKSORT v nejhorˇs´ım pˇr´ıpadˇe vyˇzaduje ˇcas Θ(n2 ), oˇcek´ avan´ y ˇcas je 9n log n, v nejn2 avan´ y poˇcet porovn´ an´ı je 1.44n log n. Potˇrebuje horˇs´ım pˇr´ıpadˇe provád´ı 2 porovnán´ı, oˇcek´ n + log n + konst pamˇeti, pouˇz´ıvá pˇr´ım´ y pˇr´ıstup k pamˇeti a nen´ı adaptivn´ı na pˇredtˇr´ıdˇené posloupnosti. HEAPSORT v nejhorˇs´ım pˇr´ıpadˇe vyˇzaduje ˇcas 20n log n, oˇcek´ avan´ y ˇcas je ≤ 20n log n, v nejhorˇs´ım i v oˇcekávaném pˇr´ıpadˇe prov´ ad´ı 2n log n porovn´ an´ı. Potˇrebuje n + konst pamˇeti, pouˇz´ıvá pˇr´ım´ y pˇr´ıstup k pamˇeti a nen´ı adaptivn´ı na pˇredtˇr´ıdˇené posloupnosti. MERGESORT v nejhorˇs´ım pˇr´ıpadˇe vyˇzaduje ˇcas 12n log n, oˇcek´ avan´ y ˇcas je ≤ 12n log n, v nejhorˇs´ım i v oˇcekávaném pˇr´ıpadˇe prov´ ad´ı n log n porovn´ an´ı (nejmenˇs´ı moˇzn´ y poˇcet). Potˇrebuje 2n + konst pamˇeti, pouˇz´ıv´ a sekvenˇcn´ı pˇr´ıstup k pamˇeti a m´ a verzi, která je adaptivn´ı na pˇredtˇr´ıdˇené posloupnosti s mal´ ym poˇctem bˇeh˚ u. A-sort v nejhorˇs´ım pˇr´ıpadˇe i v oˇcek´ aném pˇr´ıpadˇe vyˇzaduje ˇcas O(n log Fn ), kde F je poˇcet inverz´ı ve vstupn´ı posloupnosti, v nejhorˇs´ım i v oˇcek´ avaném pˇr´ıpadˇe prov´ ad´ı O(n log Fn ) porovnán´ı. Potˇrebuje 5n + konst pamˇeti, pouˇz´ıv´ a pˇr´ım´ y pˇr´ıstup k pamˇeti a je adaptivn´ı na pˇredtˇr´ıdˇené posloupnosti s mal´ ym poˇctem inverz´ı. SELECTIONSORT v nejhorˇs´ım i v oˇcek´ avaném pˇr´ıpadˇe vyˇzaduje ˇcas 2n2 , poˇcet porov2 y nán´ı v nejhorˇs´ım i v oˇcekávaném pˇr´ıpadˇe je n2 . Potˇrebuje n + konst pamˇeti, pouˇz´ıvá pˇr´ım´ pˇr´ıstup k pamˇeti a nen´ı adaptivn´ı na pˇredtˇr´ıdˇené posloupnosti. INSERTIONSORT v nejhorˇs´ım i v oˇcek´ avaném pˇr´ıpadˇe vyˇzaduje ˇcas O(n2 ), poˇcet porov2 2 nán´ı v nejhorˇs´ım pˇr´ıpadˇe je n2 , v oˇcek´ avaném pˇr´ıpadˇe n4 . Potˇrebuje n+konst pamˇeti, pouˇz´ıvá sekvenˇcn´ı pˇr´ıstup k pamˇeti a m´ a verzi, kter´ a je adaptivn´ı na pˇredtˇr´ıdˇené posloupnosti s mal´ ym poˇctem inverz´ı. Prezentované v´ ysledky byly spoˇc´ıtány pro model RAM (viz Mehlhorn 1984). Oˇcekávan´ y ˇcas pro HEAPSORT je prakticky stejn´ y jako jeho nejhorˇs´ı ˇcas. Byly navrˇzeny verze, které optimalizuj´ı poˇcet porovn´ an´ı, ale vˇetˇsinou maj´ı vˇetˇs´ı n´ aroky na ˇcas, a proto aˇz na v´ yjimky nejsou pro praktické pouˇzit´ı vhodné. Situace pro MERGESORT je komplikovanˇejˇs´ı, hodnˇe závis´ı na konkrétn´ı verzi algoritmu. Algoritmus MERGESORT je nejvhodnˇejˇs´ı pro extern´ı pamˇeti se sekvenˇcn´ım pˇr´ıstupem k dat˚ um, pro intern´ı pamˇeˇt kv˚ uli velké prostorové nároˇcnosti nen´ı doporuˇcov´ an (je napˇr. dvojn´ asobn´ a proti HEAPSORTU a témˇeˇr dvojnásobná proti QUICKSORTU). Také se hod´ı pro n´ avrh paraleln´ıch algoritm˚ u. Pro tˇr´ıdˇen´ı krátk´ ych posloupnost´ı je doporuˇcov´ ano m´ısto QUICKSORTU pro posloupnosti délky ≤ 22 pouˇz´ıt SELECTIONSORT a pro posloupnosti délky ≤ 15 INSERTIONSORT. To vede k návrhu optimalizovanéh QUICKSORTU, kter´ y, kdyˇz volá rekurzivnˇe sám sebe na krátkou posloupnost, pak pouˇzije SELECTIONSORT nebo INSERTIONSORT. V algoritmu A-sort se doporuˇcuje pouˇz´ıt (2, 3)-strom. Pomˇer ˇcas˚ u spotˇrebovan´ ych algoritmy QUICKSORT, MERGESORT a HEAPSORT na klasick´ ych poˇc´ıtaˇc´ıch uvád´ı Mehlhorn (1984) jako 1 : 1.33 : 2.22. To vˇsak nemus´ı b´ yt pravda pro souˇcasné procesory, pamˇeti a operaˇcn´ı systémy. ń´ı nestejnˇ ćh posloupnost´ı Sl´ eva e dlouhy V algoritmu MERGESORT jsme pouˇzili frontu, kter´ a ˇr´ıdila proces sluˇcov´ an´ı rostouc´ıch posloupnost´ı. Tato metoda je uspokojuj´ıc´ı a d´ av´ a optim´ aln´ı v´ ysledek (ve smyslu ˇcasové

29

nároˇcnosti), pokud posloupnosti ve frontˇe jsou stejnˇe dlouhé. Pokud se ale jejich délky hodnˇe liˇs´ı, nedosáhneme t´ımto zp˚ usobem optim´ aln´ıho v´ ysledku. Pˇritom r˚ uzné verze tohoto problému se vyskytuj´ı v mnoha u ´loh´ ach. Jednou z prvn´ıch u ´loh, kde jsme se s n´ım setkali, je konstrukce Huffmanova kódu – to je minim´ aln´ı redundantn´ı k´ od, kter´ y byl nalezen v roce 1952. K optimáln´ımu ˇreˇsen´ı vede napˇr. postup, kter´ y je kombinac´ı ‘mergeován´ı’ a optimalizace a pouˇz´ıvá metody dynamického programov´ an´ı. Nejprve form´ alnˇe pop´ıˇseme abstraktn´ı verzi tohoto problému. MERGE rost. disj. PSPstí:

Strom slučování posloupností:

Vstup: Mnoˇzina rostouc´ıch navzájem disjunktn´ıch posloupnost´ı. ´ Ukol: Pomoc´ı operace MERGE co nejrychleji spojit vˇsechny tyto posloupnosti do jediné rostouc´ı posloupnosti. Pˇredpokládejme, ˇze máme postup, kter´ y z dan´ ych rostouc´ıch posloupnost´ı vytvoˇr´ı jedinou rostouc´ı posloupnost. Tento postup urˇcuje u ´pln´ y bin´ arn´ı strom T , jehoˇz listy jsou ohodnoceny vstupn´ımi posloupnostmi a kaˇzd´ y vnitˇrn´ı vrchol je ohodnocen posloupnost´ı, která je slouˇcen´ım vstupn´ıch posloupnost´ı ohodnocuj´ıc´ıch listy v podstromu urˇceném t´ımto vrcholem. Tedy koˇren je ohodnocen v´ ystupn´ı posloupnost´ı. Form´ alnˇe pro kaˇzd´ y vnitˇrn´ı vrchol v plat´ı: kdyˇz v1 a v2 jsou synové v a P (v) je posloupnost ohodnocuj´ıc´ı vrchol v, pak P (v) =MERGE(P (v1 ), P (v2 )). Oznaˇcme l(P ) délku posloupnosti u, které v tomto procesu vyˇzaduje P P . Pak souˇcet ˇcas˚ podprocedura MERGE, je O( {l(P (v)) | v je vnitˇrn´ı vrchol stromu T }). Indukc´ı lehce dostaneme, ˇze X

{l(P (v)) | v vnitˇrn´ı vrchol stromu T } =

X

d(t)l(P (t)),

{t je list T }

kde d(t) je hloubka listu t. Kdyˇz tedy T je u ´pln´ y binárn´ı strom, jehoˇz listy jsou ohodnoceny navz´ ajem disjunktn´ımi rostouc´ımi posloupnostmi, pak následuj´ıc´ı algoritmus Slevani spoj´ı tyto posloupnosti do jediné rostouc´ı posloupnosti a procedury MERGE budou vyˇzadovat celkov´ y ˇcas O(

X

d(t)l(P (t))).

{t je list T }

Slevani(T, {P (l) | l je list T }) while P (koˇren T ) nen´ı definováno do v := vrchol T takov´ y, ˇze P (v) nen´ı definov´ ano a pro oba syny v1 a v2 vrcholu v jsou P (v1 ) a P (v2 ) definov´ any P (v) :=MERGE(P (v1 ), P (v2 )) enddo Nyn´ı m˚ uˇzeme pˇreformulovat p˚ uvodn´ı problém: Vstup: n ˇc´ısel x1 , x2 , . . . , xn V´ ystup: u ´pln´ y binárn´ı strom T s n listy a bijekce φ z mnoˇziny {1, 2, . . . , n} do list˚ u T

30 Def optimálního stromu:

Pn taková, ˇze i=1 d(φ(i))xi je minim´ aln´ı (kde d(φ(i)) je hloubka listu φ(i)). ˇ Rekneme, ˇze dvojice (T, φ) je optim´ aln´ı strom vzhledem k x1 , x2 , . . . , xn . V pˇreformulováné u ´loze uˇz nepracujeme s posloupnostmi, ale jen s jejich délkami. To znamená, ˇze kdyˇz pro p˚ uvodn´ı u ´lohu byly vstupem posloupnosti P1 , P2 , . . . , Pn , pak pro pˇreformulovanou u ´lohu jsou vstupem jen délky l(P1 ), l(P2 ), . . . , l(Pn ). Strom vytvoˇren´ y pro pˇreformulovanou u ´lohu je pouˇzit v algoritmu Slevani tak, ˇze posloupnost Pi ohodnocuje list, kter´ y byl v pˇreformulované u ´loze ohodnocen délkou l(Pi ), a hledan´ a posloupnost v p˚ uvodn´ı u ´loze ohodnocuje koˇren stromu.

Def hodnoty Cont:

Mˇejme mnoˇzinu {xi | i = 1, 2, . . . , n}. Pro u ´pln´ y bin´ arn´ı strom T s n listy a bijekci φ z mnoˇziny {1, 2, . . . , n} do list˚ u stromu T definujme Cont(T, φ) =

n X

d(φ(i))xi ,

i=1

kde d(φ(i)) je hloubka listu φ(i), tj. délka cesty z koˇrene do listu φ(i) pro i = 1, 2, . . . , n. Chceme zkonstruovat u ´pln´ y binárn´ı strom s n listy, kter´ y minimalizuje hodnotu Cont. K ˇreˇsen´ı pouˇzijeme následuj´ıc´ı algoritmus, kter´ y je upravenou verz´ı hladového algoritmu pro náˇs problém. Optim(x1 , x2 , . . . xn ): V je mnoˇzina n jednoprvkov´ ych strom˚ u [Jednotlivé listy φ je bijekce mezi {1, 2, . . . , n} a mnoˇzinou V for every v ∈ V do c(v) := xφ−1 (v) enddo while |V | > 1 do vezmi z V dva stromy v1 a v2 s nejmenˇs´ım ohodnocen´ım odstraˇ n je z V vytvoˇr nov´ y strom v spojen´ım strom˚ u v1 a v2 c(v) := c(v1 ) + c(v2 ), strom v vloˇz do V enddo V´ ystup: (T, φ), kde T je strom v mnoˇzinˇe V

se pak ohodnotí hodnotami x_i]

Spojuju stromy s nejmenšími hodnotami.

Vytvoˇren´ı nového stromu v spojen´ım strom˚ u v1 a v2 znamen´ a vytvoˇren´ı nového vrcholu, kter´ y bude koˇrenem stromu v a jehoˇz synové budou koˇreny strom˚ u v1 a v2 . To je analogické proceduˇre spoj. Vˇ eta. Pro danou posloupnost ˇc´ısel (x1 , x2 , . . . , xn ) algoritmus Optim nalezne optim´ aln´ı strom pro mnoˇzinu x1 , x2 , . . . , xn a pokud je posloupnost (x1 , x2 , . . . , xn ) neklesaj´ıc´ı, pak vyˇzaduje ˇcase O(n). D˚ ukaz. D˚ ukaz má dvˇe ˇcásti. V prvn´ı dok´ aˇzeme korektnost algoritmu a ve druhé pop´ıˇseme reprezentaci mnoˇziny V a vypoˇcteme ˇcasovou sloˇzitost. Nejprve pˇripomeˇ nme, ˇze φ(i) je list T pro kaˇzdé i ∈ {1, 2, . . . , n}. Protoˇze na zaˇcátku V obsahuje jen jednoprvkové stromy, tak tvrzen´ı plat´ı. Kaˇzd´ y bˇeh cyklu while do zmenˇs´ı poˇcet strom˚ u V o jeden, ale nezmˇen´ı mnoˇzinu list˚ u. Proto T je strom s n listy, φ je bijekce z {1, 2, . . . , n} do mnoˇziny list˚ u T a algoritmus vˇzdy konˇc´ı. Dok´ aˇzeme indukc´ı podle n, ˇze zkonstruovaná dvojice (T, φ) je optim´ aln´ı strom vzhledem k (x1 , x2 , . . . , xn ).

31

Strom T' Jen info, co nám dává indukční předpoklad:

Kdyˇz n = 2, tvrzen´ı zˇrejmˇe plat´ı. Pˇredpokl´ adejme, ˇze plat´ı pro kaˇzdou posloupnost ˇc´ısel ˇ ´jmy na (y1 , y2 , . . . ,yn−1 ), a necht x1 ≤ x2 ≤ · · · ≤ xn je neklesaj´ıc´ı posloupnost ˇc´ısel. Bez u obecnosti m˚ uˇzeme pˇredpokládat, ˇze v prvn´ım kroku algoritmus Optim zvolil stromy φ(1) a φ(2). Uvaˇzujme mnoˇzinu (y1 , y2 , . . . , yn−1 ), kde yi = xi+2 pro i = 1, 2, . . . , n−2, yn−1 = x1 + x2 . Nechˇt T ′ je strom z´ıskan´ y ze stromu T odstranˇen´ım list˚ u φ(1) a φ(2) a nechˇt ψ je bijekce z mnoˇziny {1, 2, . . . , n −1} taková, ˇze ψ(i) = φ(i+2) pro i = 1, 2, . . . , n −2 a ψ(n −1) je otec listu φ(1). Pak m˚ uˇzeme pˇredpokládat, ˇze algoritmus Optim(y1 , y2 , . . . , yn−1 ) zkonstruoval strom (T ′ , ψ), a podle indukˇcn´ıho pˇredpokladu je to optim´ aln´ı strom pro (y1 , y2 , . . . , yn−1 ). ˇ Necht (U, θ) je optimáln´ı strom vzhledem k (x1 , x2 , . . . , xn ). Zvolme vnitˇrn´ı vrchol u stromu U takov´ y, ˇze délka cesty z koˇrene do vrcholu u je nejvˇetˇs´ı mezi vˇsemi vnitˇrn´ımi vrcholy stromu U . Nechˇt u1 a u2 jsou synové u, pak nutnˇe u1 a u2 jsou listy stromu U . Nechˇt i, j ∈ {1, 2, . . . , n} takové, ˇze θ(i) = u1 , θ(j) = u2 . Po eventu´ aln´ım pˇrejmenov´ an´ı m˚ uˇzeme pˇredpokládat, ˇze kdyˇz i, j ∈ {1, 2}, pak i = 1 a j = 2. Definujme η z {1, 2, . . . , n} do list˚ u U tak, ˇze η(1) = u1 , η(2) = u2 , η(i) = θ(1), η(j) = θ(2) a η(k) = θ(k) pro vˇsechna k ∈ {3, 4, . . . , n} \ {i, j}. Pak η je bijekce a Cont(U, η) − Cont(U, θ) = (d(u1 ) − d(θ(1))(x1 − xi ) + (d(u2 ) − d(θ(2))(x2 − xj ). Z volby u plyne, ˇze d(u1 ) ≥ d(θ(1)), d(u2 ) ≥ d(θ(2)), x1 ≤ xi a x2 ≤ xj . Odtud (d(u1 ) − d(θ(1))(x1 − xi ) + (d(u2 ) − d(θ(2))(x2 − xj ) ≤ 0 a protoˇze (U, θ) je optimáln´ı strom pro (x1 , x2 , . . . , xn ), dost´ av´ ame, ˇze (U, η) je také optimáln´ı strom pro (x1 , x2 , . . . , xn ). Odstranˇen´ım list˚ u u1 a u2 ze stromu U dostaneme strom U ′ . Definujme τ z {1, 2, . . . , n − 1} pˇredpisem τ (i) = η(i + 2) pro i = 1, 2, . . . , n − 2 a τ (n − 1) = u. Pak τ je bijekce z {1, 2, . . . , n − 1} do mnoˇziny list˚ u U ′ a protoˇze (T ′ , ψ) je optimáln´ı strom pro (y1 , y2 , . . . , yn−1 ), plat´ı, ˇze Cont(T ′ , ψ) ≤ Cont(U ′ , τ ). Protoˇze Cont(T, φ) = Cont(T, ψ) + x1 + x2 , Cont(U, η) = Cont(U ′ , τ ) + x1 + x2 pak závˇer je, ˇze (T, φ) je optimáln´ı strom pro (x1 , x2 , . . . , xn ).

Druhá část důkazu (čas. slož.)

Pˇredpokládejme opˇet, ˇze x1 ≤ x2 ≤ · · · ≤ xn a ˇze v daném okamˇziku jsou v1 , v2 , . . . , vk postupnˇe vytvoˇrené v´ıceprvkové stromy (tj. strom vi byl vytvoˇren pˇred stromem vj , kdyˇz i < j). V tomto okamˇziku je mnoˇzina V sjednocen´ım mnoˇziny {v1 , v2 , . . . , vk } a mnoˇziny jednoprvkov´ ych strom˚ u, které nebyly jeˇstˇe zpracov´ any. Nyn´ı vytvoˇr´ıme strom w spojen´ım strom˚ u t1 a t2 s nejmenˇs´ım ohodnocen´ım. Z popisu algoritmu plyne, ˇze kdyˇz strom vi pro i = 1, 2, . . . , k vznikl spojen´ım strom˚ u u1 a u2 , pak max{c(u1 ), c(u2 )} ≤ min{c(t1 ), c(t2 )}, a proto c(w) ≥ c(vi ) pro kaˇzdé i = 1, 2, . . . , k. Pak indukc´ı okamˇzitˇe dostáváme, ˇze c(v1 ) ≤ c(v2 ) ≤ · · · ≤ c(vk ). Tedy staˇc´ı, abychom mˇeli rostouc´ı posloupnost list˚ u a v n´ı ukazatel na nejmenˇs´ı list, kter´ y je jeˇstˇe nezpracovan´ ym jednoprvkov´ ym stromem (tj.

32

pˇred ukazatelem jsou listy, které uˇz nejsou stromy v mnoˇzinˇe V , za ukazatelem jsou listy, které jsou jeˇstˇe jednoprvkové stromy v mnoˇzinˇe V ) a frontu v´ıceprvkov´ ych strom˚ u (z n´ıˇz stromy ke zpracován´ı odeb´ıráme zpˇredu a novˇe vytvoˇrené ukl´ ad´ ame na konec). Udrˇzovat tyto struktury vyˇzaduje ˇcas O(1) stejnˇe jako nalezen´ı dvou strom˚ u s nejmenˇs´ım ohodnocen´ım. M˚ uˇzeme tedy shrnout, ˇze algoritmus Optim konstruuje optim´ aln´ı stromy v ˇcase O(n), kde n je poˇcet zadan´ ych ˇc´ısel xi . Pro aplikaci na naˇsi p˚ uvodn´ı u ´lohu je tˇreba jeˇstˇe setˇr´ıdit vstupn´ı posloupnost délek pro pˇreformulovanou u ´lohu. Tato posloupnost je tvoˇrena pˇrirozen´ ymi ˇc´ısly a k jej´ımu setˇr´ıdˇen´ı m˚ uˇzeme pouˇz´ıt algoritmus BUCKETSORT (bude pops´ an d´ ale v textu), kter´ y vyˇzaduje ˇcas O(n + m), kde n je poˇcet posloupnost´ı a m je maxim´ aln´ı délka posloupnosti. Vˇ eta. Uveden´ y algoritmus mnoˇzinu disjunktn´ıch rostouc´ıch posloupnost´ı P1P , P2 , . . . , Pn o n délk´ ach l(P1 ), l(P2 ), . . . , l(Pn ) spoj´ı do jediné rostouc´ı posloupnosti v ˇcase O( i=1 l(Pi )).

VIII. Rozhodovac´ı stromy Vˇetˇsina obecn´ ych tˇr´ıdic´ıch algoritm˚ u pouˇz´ıv´ a jedinou primitivn´ı operaci mezi prvky vstupn´ı posloupnosti, a to jejich vzájemné porovn´ an´ı. To znamen´ a, ˇze pr´ aci takového algoritmu lze popsat binárn´ım stromem, jehoˇz vnitˇrn´ı vrcholy jsou ohodnoceny porovn´ an´ımi dvojic prvk˚ u ´jmy na obecnosti pˇredpokl´ adejme, ˇze vstupn´ı vstupn´ı posloupnosti (napˇr. ai < aj ). Bez u posloupnost je permutace π mnoˇziny {1, 2, . . . , n}. Tato permutace proch´ az´ı stromem takto: Zaˇc´ıná v koˇreni stromu. Kdyˇz je ve vnitˇrn´ım vrcholu v ohodnoceném porovnán´ım ai ≤ aj , pak kdyˇz π(i) < π(j), pokraˇcuje v levém synu vrcholu v, a kdyˇz π(j) < π(i), pokraˇcuje v pravém synu vrcholu v. Proces tˇr´ıdˇen´ı konˇc´ı, kdyˇz se dostane do listu.

Aby byl algoritmus korektn´ı, mus´ı platit, ˇze dvˇe r˚ uzné permutace skonˇc´ı v r˚ uzn´ ych listech. Tedy strom popisuj´ıc´ı korektn´ı algoritmus pro setˇr´ıdˇen´ı n-prvkov´ yvh posloupnost´ı mus´ı m´ıt alespoˇ n n! list˚ u. Délka cesty z koˇrene do listu, kde skonˇcila permutace π, reprezentuje poˇcet porovnán´ı, které potˇrebuje dan´ y algoritmus k setˇr´ıdˇen´ı dané posloupnosti π. Protoˇze porovnán´ı vyˇzaduje alespoˇ n jednotku ˇcasu, dost´ av´ ame t´ım i doln´ı odhad na ˇcas potˇrebn´ yk setˇr´ıdˇen´ı této posloupnosti algoritmem odpov´ıdaj´ıc´ım danému stromu. Doln´ı odhad poˇctu porovnán´ı i ˇcasu pro dan´ y algoritmus a vˇsechny n-prvkové posloupnosti je pak délka nejdelˇs´ı cesty z koˇrene do listu v odpov´ıdaj´ıc´ım stromu. To n´ am umoˇzn ˇuje z´ıskat obecnˇe platn´ y doln´ı odhad ˇcasu potˇrebného k setˇr´ıdˇen´ı n−prvkové posloupnosti, kter´ ym je minimum pˇres vˇsechny binárn´ı stromy s alespoˇ n n! listy z jejich maxim´ aln´ıch délek cest z koˇrene do listu. Korektnost tˇechto u ´vah plyne z pozorov´ an´ı, ˇze kdyˇz porovn´ an´ı je jedin´ a primitivn´ı operace, pak algoritmus nen´ı závisl´ y na konkrétn´ıch prvc´ıch vstupn´ı posloupnosti, ale jen na jejich vzájemném vztahu. Proto staˇc´ı uvaˇzovat pouze permutace n-prvkové mnoˇziny, protoˇze zachycuj´ı vˇsechny moˇzné vztahy v n-prvkové posloupnosti. D´ ale je tˇreba si uvˇedomit, ˇze vztah mezi stromem pro n-prvkové posloupnosti a stromem pro (n + 1)-prvkové posloupnosti je dán konkrétn´ım algoritmem a nedá se popsat obecnˇe. V nevhodném algoritmu se m˚ uˇze st´ at, ˇze v nˇekterém listu neskonˇc´ı ˇz´ adn´ a permutace. To nastane, kdyˇz strom pro n-prvkové posloupnosti m´ a v´ıce neˇz n! list˚ u, nebo, jinak ˇreˇceno, kdyˇz porovnán´ı dvou stejn´ ych prvk˚ u se na nˇejaké cestˇe vyskytne alespoˇ n dvakrát.

33

a1 < a2

a1 < a3

a2 < a3

a2 < a3

a1 < a2

a1 , a2 , a3 a1 , a3 , a2 a3 , a1 , a2

a1 < a3

a2 , a1 , a3 a2 , a3 , a1

a1 < a2

a3 , a2 , a1

Obr. 1 Následuj´ıc´ı obrázek ilustruje naˇse u ´vahy na SELECTIONSORTU pro 3-prvkové posloupnosti. Listy jsou ohodnoceny permutacemi vstupn´ı mnoˇziny {a1 , a2 , a3 }, které v nich skonˇc´ı, nebo jsou prázdné. Definice. Mˇejme tˇr´ıdic´ı algoritmus A, kter´ y jako jedinou primitivn´ı operaci s prvky vstupn´ı ˇ posloupnosti pouˇz´ıvá jejich porovn´ an´ı. Rekneme, ˇze bin´ arn´ı strom T , jehoˇz vnitˇrn´ı vrcholy jsou ohodnoceny porovnán´ımi ai ≤ aj pro i, j = 1, 2, . . . , n, i 6= j, je rozhodovac´ım stromem algoritmu A pro n-prvkové posloupnosti, kdyˇz pro kaˇzdou permutaci π n-prvkové mnoˇziny plat´ı posloupnost porovnán´ı pˇri tˇr´ıdˇen´ı permutace π algoritmem A je stejná jako posloupnost porovnán´ı pˇri pr˚ uchodu permutace π stromem T . Korektnost algo. a dolní odhad času:

Pak korektnost algoritmu zajiˇsˇtuje, ˇze dvˇe r˚ uzné permutace mnoˇziny {1, 2, . . . , n} skonˇc´ı v r˚ uzn´ ych listech stromu T a doln´ım odhadem pro ˇcas algoritmu A v nejhorˇs´ım pˇr´ıpadˇe je délka nejdelˇs´ı cesty z koˇrene do listu. Pˇri rovnomˇerném rozdˇelen´ı vstupn´ıch posloupnost´ı je oˇcekávan´ y ˇcas algoritmu A roven pr˚ umˇerné délce cesty z koˇrene do listu. Definujme S(n) jako minimum pˇres vˇsechny stromy T s alespoˇ n n! listy z délek nejdelˇs´ıch cest z koˇrene do listu v T , A(n) jako minimum pˇres vˇsechny stromy T s alespoˇ n n! listy z pr˚ umˇern´ ych délek cest z koˇrene do listu v T . Naˇs´ım c´ılem je spoˇc´ıtat doln´ı odhady tˇechto veliˇcin.

Odhad S(n)

Kdyˇz nejdelˇs´ı cesta z koˇrene do listu v bin´ arn´ım stromˇe T m´ a délku k, pak T m´ a nejv´ yˇse 2k S(n) list˚ u. Proto n! ≤ 2 . Odtud plyne, ˇze S(n) ≥ log2 n!. Pˇripomeˇ nme si Stirling˚ uv vzorec pro faktoriál: √ n n 1 1 n! = 2πn (1 + + O( 2 )). e 12n n Protoˇze pro n ≥ 1 je

1 , 1 12n n2

≥ 0, m˚ uˇzeme pˇredpokl´ adat, ˇze (1 +

1 12n

+ O( n12 )) ≥ 1 pro

34

vˇsechna n ≥ 1. Po zlogaritmován´ı vzorce dost´ av´ ame log2 n! ≥

√ 1 1 log2 n + n(log2 n − log2 e) + log2 2π ≥ (n + ) log2 n − n log2 e. 2 2

Protoˇze e1 = e = 2log2 e = (eln 2 )log2 e = eln 2 log2 e , plat´ı, ˇze

1 ln 2

= log2 e, a tedy 1 n S(n) ≥ log2 n! ≥ (n + ) log2 n − . 2 ln 2

Odhad A(n)

Dále pro binárn´ı strom T oznaˇcme B(T ) souˇcet vˇsech délek cest z koˇrene do list˚ u a poloˇzme B(k) = min{B(T ) | T je bin´ arn´ı strom s k listy}. Kdyˇz ukáˇzeme, ˇze B(k) ≥ k log2 k, pak bude A(n) ≥

Důkaz indukcí: kořen

T1 k1 listů

T2 k2 listů

1 n n! log2 n! B(n!) ≥ = log2 n! ≥ (n + ) log2 n − . n! n! 2 ln 2

Dokaˇzme tedy, ˇze B(T ) ≥ k log2 k pro kaˇzd´ y bin´ arn´ı strom T s k listy. Kdyˇz ve stromˇe T vynech´ ame kaˇzd´ y vrchol, kter´ y m´ a jen jednoho syna, a tohoto syna spoj´ıme s jeho pˇredch˚ udcem, dostaneme u ´pln´ y bin´ arn´ı strom T ′ s k listy takov´ y, ˇze B(T ′ ) ≤ B(T ). Proto se staˇc´ı omezit na u ´plné binárn´ı stromy. Kdyˇz T je u ´pln´ y bin´ arn´ı strom s jedn´ım listem, pak B(T ) = 0 = 1 log2 1, kdyˇz T je u ´pln´ y bin´ arn´ı strom se dvˇema listy, pak B(T ) = 2 = 2 log2 2. Tedy plat´ı B(1) ≥ 1 log2 1 a B(2) ≥ 2 log2 2. Pˇredpokl´ adejme, ˇze B(i) ≥ i log2 i pro i < k, a nechˇt T je u ´pln´ y binárn´ı strom s k listy. Nechˇt T1 a T2 jsou podstromy urˇcené syny koˇrene a nechˇt Ti má ki list˚ u, kde i = 1, 2. Pak 1 ≤ k1 , k2 a k1 + k2 = k, tedy k1 , k2 < k a podle indukˇcn´ıho pˇredpokladu B(ki ) ≥ ki log2 ki . Odtud B(T ) = k1 + B(T1 ) + k2 + B(T2 ) ≥ k + B(k1 ) + B(k2 ) ≥ k + k1 log2 k1 + k2 log2 k2 . Tedy staˇc´ı ukázat, ˇze k + k1 log2 k1 + k2 log2 k2 ≥ k log2 k pro vˇsechna k1 , k2 > 0 taková, ˇze k = k1 + k2 . To je ekvivalentn´ı s tvrzen´ım, ˇze pro k > 0 plat´ı f (x) = x log2 x + (k − x) log2 (k − x) + k − k log2 k ≥ 0, kde x ∈ (0, k). Abychom to dokázali, vˇsimnˇeme si, ˇze f ( k2 ) = 0 a poˇc´ıtejme derivaci f . f ′ (x) = log2 x + log2 e − log2 (k − x) − log2 e = log2

x . k−x

Nyn´ı kdyˇz x ∈ (0, k2 ), pak f ′ (x) < 0 a f je na tomto intervalu klesaj´ıc´ı, kdyˇz x ∈ ( k2 , k), pak f ′ (x) > 0 a f je na tomto intervalu rostouc´ı. Odtud plyne, ˇze f (x) ≥ 0 pro x ∈ (0, k). T´ım jsme dokázali, ˇze A(n) ≥ (n + 12 ) log2 n − lnn2 . Shrneme naˇse v´ ysledky.

35

Vˇ eta. Kaˇzd´ y tˇr´ıdic´ı algoritmus, jehoˇz jedinou primitivn´ı operac´ı s prvky vstupn´ı posloupnosti je porovn´ an´ı, vyˇzaduje v nejhorˇs´ım i v oˇcek´ avaném pˇr´ıpadˇe alespoˇ n cn log n ˇcasu pro nˇejakou konstantu c > 0. V nejhorˇs´ım pˇr´ıpadˇe pouˇzije alespoˇ n ⌈(n + 12 ) log2 n − lnn2 ⌉ porovn´ an´ı a oˇcek´ avan´ y poˇcet porovn´ an´ı pˇri rovnomˇerném rozdˇelen´ı vstupn´ıch posloupnost´ı 1 n je alespoˇ n (n + 2 ) log2 n − ln 2 . Tato vˇeta plat´ı i pro ˇsirˇs´ı tˇr´ıdu primitivn´ıch operac´ı, proto v n´ı lze oslabit pˇredpklady. Doln´ı odhad (v nejhorˇs´ım i pr˚ umˇerném pˇr´ıpadˇe) bude platit i za pˇredpokladu, ˇze tˇr´ıdic´ı algoritmus nepouˇz´ıvá nepˇr´ımé adresován´ı a celoˇc´ıselné dˇelen´ı. (Na druhé stranˇe n´ asleduj´ıc´ı klasick´ y algoritmus BUCKETSORT ukazuje, ˇze pˇredpoklady ve vˇetˇe nelze zcela vynechat.) Tato metoda pro nalezen´ı doln´ıho odhadu se pouˇz´ıv´ a i pro vyˇc´ıslov´ an´ı algebraick´ ych funkc´ı a pˇri algoritmickém ˇreˇsen´ı geometrick´ ych u ´loh.

IX. Pˇrihr´ adkové tˇr´ıdˇen´ı Vlastnosti struktury:

V následuj´ıc´ıch algoritmech pˇredpokl´ ad´ ame, ˇze Qi jsou spojové seznamy, nov´ y prvek se vkládá na konec seznamu a konkatenace seznam˚ u z´ avis´ı na jejich poˇrad´ı. V seznamech máme okamˇzit´ y pˇr´ıstup k prvn´ımu a posledn´ımu prvku (pomoc´ı ukazatel˚ u na tyto prvky). Algoritmus BUCKETSORT tˇr´ıd´ı posloupnost pˇrirozen´ ych ˇc´ısel a1 , a2 , . . . , an z intervalu < 0, m >. BUCKETSORT(a1 , a2 , . . . , an , m): for every i = 0, 1, . . . , m do Qi = ∅ enddo for every i = 1, 2, . . . , n do ai vloˇz na konec seznamu Qai enddo i := 0, P := ∅ while i ≤ m do P :=konkatenace P a Qi , i := i + 1 enddo V´ ystup: P je neklesaj´ıc´ı posloupnost prvk˚ u a 1 , a 2 , . . . , an Algoritmus nevyˇzaduje, aby prvky ve vstupn´ı posloupnosti byly r˚ uzné. Ve v´ ystupn´ı posloupnosti se dan´ y prvek opakuje tolikrát, kolikr´ at se opakoval ve vstupn´ı posloupnosti, se zachován´ım poˇrad´ı (tj. tˇr´ıdˇen´ı je stabiln´ı). Konkatenace dvou seznam˚ u a vloˇzen´ı prvku do seznamu vyˇzaduj´ı ˇcas O(1). Proto prvn´ı a tˇret´ı cyklus vyˇzaduj´ı ˇcas O(m) a druh´ y cyklus ˇcas O(n). Celkem algoritmus vyˇzaduje O(n + m) ˇcasu a pamˇeti. Zˇrejmˇe kdyˇz m = O(n), tak pro tento algoritmus neplat´ı tvrzen´ı vˇety z pˇredchoz´ıho odstavce. D˚ uvodem je, ˇze nejsou splnˇeny pˇredpoklady, protoˇze druh´ y cyklus pouˇz´ıv´ a nepˇr´ımé adresov´ an´ı.

Varianty Bucketsortu:

Nyn´ı uvedeme dvˇe sofistikovanˇejˇs´ı verze tohoto algoritmu. V prvn´ı pˇredpokládáme, ˇze a1 , a2 , . . . , an je posloupnost navzájem r˚ uzn´ ych re´ aln´ ych ˇc´ısel z intervalu < 0, 1 > a α je pevnˇe zvolené kladné reálné ˇc´ıslo. HYBRIDSORT(a1 , a2 , . . . , an ): k := αn for every i = 0, 1, . . . , k do Qi = ∅ enddo

36

for every i = 1, 2, . . . , n do ai vloˇz na konec seznamu Q⌈kai ⌉ enddo i := 0, P := ∅ while i ≤ k do HEAPSORT(Qi ) P :=konkatenace P a Qi , i := i + 1 enddo V´ ystup: P je rostouc´ı posloupnost prvk˚ u a 1 , a 2 , . . . , an

[Skutečně HEAPSORT!]

Vˇ eta. Algoritmus HYBRIDSORT setˇr´ıd´ı posloupnost re´ aln´ ych ˇc´ısel z intervalu < 0, 1 > v nejhorˇs´ım pˇr´ıpadˇe v ˇcase O(n log n). Kdyˇz prvky ai maj´ı rovnomˇerné rozloˇzen´ı a jsou na sobˇe nez´ avislé, pak oˇcek´ avan´ y ˇcas je O(n). Nejhorší případ:

D˚ ukaz. Prvn´ı dva cykly v algoritmu vyˇzaduj´ı ˇcas O(n), i-t´ y bˇeh tˇret´ıho cyklu vyˇzaduje [while cyklu] nejv´ yˇse ˇcas O(1 + |Qi | log |Qi |). Proto ˇcas celého tˇret´ıho cyklu je k k k X X X |Qi |) log n) = O(n log n) O( (1 + |Qi | log |Qi |) = O( (1 + |Qi | log n) = O(k + ( i=0

i=0

i=0

a celkov´ y ˇcas HYBRIDSORTU v nejhorˇs´ım pˇr´ıpadˇe je nejv´ yˇse O(n log n). Nyn´ı odhadneme oˇcekávan´ y ˇcas. Poloˇzme Xi = |Qi |. Pak Xi je n´ ahodn´ a promˇenná a 1 protoˇze pravdˇepodobnost, ˇze x ∈ Qi , je k , dost´ av´ ame, ˇze n 1 q 1 Prob(Xi = q) = ( ) (1 − )n−q . q k k Oˇcekávan´ y ˇcas vyˇzadovan´ y tˇret´ım cyklem se pak rovn´ a k X

n X

n 1 q 1 n(n − 1) n E( 1 + Xi log Xi ) ≤ k + k q ( ) (1 − )n−q = k + k( + ) = O(n), q k k k2 k q=2 i=0 2

protoˇze k = αn a n n−2 n−1 2 n q = (q(q − 1) + q) = n(n − 1) +n . q q q−2 q−1 (Jedná se vlastnˇe o znám´ y v´ ypoˇcet 2. momentu binomického rozdˇelen´ı).

Poznámka: V d˚ ukazu jsme pouˇzili odhad q log q ≤ q 2 a d˚ usledkem toho je, ˇze jsme dokázali, ˇze oˇcekávaná sloˇzitost HYBRIDSORTU z˚ ustane line´ arn´ı, i kdybychom v nˇem m´ısto HEAPSORTU pouˇzili nˇejak´ y tˇr´ıdic´ı algoritmus s kvadratickou sloˇzitost´ı, napˇr. INSERTIONSORT. Druhá modifikace BUCKETSORTU:

Nyn´ı pouˇzijeme modifikaci BUCKETSORTU pro tˇr´ıdˇen´ı slov. M´ ame tot´ alnˇe uspoˇrádanou abecedu a chceme lexikograficky setˇr´ıdit slova a1 , a2 , . . . , an nad touto abecedou. Pˇripomeˇ nme, ˇze kdyˇz a = x1 x2 . . . xn a b = y1 y2 . . . ym jsou dvˇe slova nad tot´ alnˇe uspoˇr´ adanou abecedou Σ, pak a < b v lexikografickém uspoˇr´ ad´ an´ı, pr´ avˇe kdyˇz existuje i = 0, 1, . . . , min{n, m}

37

ˇ n = i < m nebo i < min{n, m} a takové, ˇze xj = yj pro kaˇzdé j = 1, 2, . . . , i a bud l(i) xi+1 < yi+1 . Pˇredpokládejme, ˇze ai = a1i a2i . . . ai , kde aji ∈ Σ a l(i) je délka i-tého slova ai .

Do S_i si uložím jaká různá písmenka se vyskytují jako i tý znak ve všech slovech

Projdu všechna slova v T a rozhodím je do kbelíků podle i tého písmenka.

WORDSORT(a1 , a2 , . . . , an ): for every i = 1, 2, . . . , n do l(i) :=délka slova ai enddo [Spočítám si délky slov] l = max{l(i) | i = 1, 2, . . . , n} [Spočítám si nejdelší délku slova] for every i = 1, 2, . . . , l do Li = ∅ enddo [Inicializuji si seznamy pro slova dané délky] for every i = 1, 2, . . . , n do [Podle délky vkládám slova do správných seznamů] ai vloˇz do Ll(i) enddo Komentáˇr: Pro kaˇzdé i obsahuje Li vˇsechna slova z mnoˇziny {a1 , a2 , . . . , an } délky i. P := {(j, aji ) | 1 ≤ i ≤ n, 1 ≤ j ≤ l(i)} [Seznam dvojic (i tý znak slova, znak)] P1 :=BUCKETSORT(P ) podle druhé komponenty [Mám setřízeno podle písmenek tedy] P2 :=BUCKETSORT(P1 ) podle prvn´ı komponenty [Setříděno podle 1. a 2. komponenty!!] for every i = 1, 2, . . . , l do Si = ∅ enddo (i, x) :=prvn´ı prvek P2 while (i, x) 6= N IL do (i, x) vloˇz do Si while(i, x) =následn´ık (i, x) v P2 do [Porovnávají se obě složky dvojice, nechceme vkládat vícekrát prvek (i,x)] (i, x) :=následn´ık (i, x) v P2 enddo (i, x) :=následn´ık (i, x) v P2 [Tento řádek je tu navíc??? Ano!!] enddo Komentáˇr: V Si jsou vˇsechny dvojice (i, x) takové, ˇze x je i-t´ ym p´ısmenem nˇekterého vstupn´ıho slova a kdyˇz x < y, pak (i, x) je pˇred (i, y). Příklad ====================== for every s ∈ Σ do Ts := ∅ enddo a1 = angl (začátek slova anglie :)) T := ∅, i := l a2 = ano while i > 0 do [For cyklus od i:= l (el) downto 1 (jedna)] L_4 = {angl}, L_3 = {ano} T := konkatenace Li a T , a :=prvn´ı slovo v T P = {(1,a),(2,n),(3,g),(4,l), while a 6= N IL do (1,a),(2,n),(3,o)} s := i-té p´ısmeno a, vloˇz a do Ts P1= {(1,a),(1,a),(4,l) (2,n),(2,n}, a :=následn´ık a v T (3,g),(3,o)} enddo P2= {(1,a),(1,a), (2,n),(2,n}, (i, x) :=prvn´ı prvek v Si , T := ∅ [Tady se maže T!] (3,g),(3,o),(4,l)} while (i, x) 6= N IL do S1 = {(1,a)} T := konkatenace T a Tx , Tx := ∅ S2 = {(2,n)} (i, x) :=následn´ık (i, x) v Si S3 = {(3,g),(3,o)} enddo 1. běh while cyklu i := i − 1 T = {angl} enddo T_l = {angl} V´ ystup: T je setˇr´ıdˇená posloupnost slov a1 , a2 , . . . , an Uvaˇzujme jeden bˇeh posledn´ıho cyklu algortimu pro urˇcité i. Po jeho skonˇcen´ı jsou v T vˇsechna slova z mnoˇziny a1 , a2 , . . . , an , kter´ a maj´ı délku alespoˇ n i, a kdyˇz slovo ar je pˇred k k aq v seznamu T , pak existuje j = i−1, i, . . . , l takové, ˇze ar = aq pro kaˇzdé k = i, i+1, . . . , j

38

Časová složitost:

ˇ l(r) = j ≤ l(q) nebo j < min{l(r), l(q)} a aj+1 < aj+1 . To plyne z vlastnost´ı algoritmu a bud r q BUCKETSORT indukc´ı podle i. Jedin´ y a hlavn´ı rozd´ıl proti BUCKETSORTU je, ˇze azdné. To n´ am zajiˇsˇtuje mnoˇzina Si neprocház´ıme vˇsechny pˇrihrádky Tx , ale pouze nepr´ (viz Komentáˇr). Pn Oznaˇcme L = i=1 l(i) a pˇripomeˇ nme, ˇze l = max{l(i) | i = 1, 2, . . . , n}. Pak prvn´ı cyklus (v´ ypoˇcet délek slov) vyˇzaduje ˇcas O(L). Druh´ y cyklus (inicializace seznam˚ u Li ) vyˇzaduje ˇcas O(l) = O(L) a tˇret´ı cyklus (zaˇrazen´ı slov do Li podle délek) ˇcas O(n) = O(L). Vytvoˇren´ı seznamu P vyˇzaduje ˇcas O(L) a jeho setˇr´ıdˇen´ı podle obou komponent ˇcas O(L + l) = O(L), protoˇze P i P1 maj´ı nejv´ yˇse L prvk˚ u. Dalˇs´ı cyklus (zaloˇzen´ı seznam˚ u Si ) vyˇzaduje ˇcas O(l) a následuj´ıc´ı cyklus vytváˇrej´ıc´ı seznamy Si ˇcas O(L). Cyklus zakl´ adaj´ıc´ı seznamy Tx vyˇzaduje ˇcas O(|Σ|). Bˇehy dalˇs´ıho cyklu jsou indexov´ any i = 1, 2, . . . , l. Pro kaˇzdé i oznaˇcme mi Pl poˇcet slov z mnoˇziny {a1 , a2 , . . . , an }, kter´ a maj´ı délku alespoˇ n i. Pak L = i=1 mi a prvn´ı vnitˇrn´ı cyklus v i-tém bˇehu vnˇejˇs´ıho cyklu vyˇzaduje ˇcas O(mi ) a druh´ y vnitˇrn´ı cyklus ˇcas y ˇcas algoritmu je O(L + m), kde m = |Σ| a L je souˇcet délek O(|Si |) = O(mi ). Tedy celkov´ vˇsech slov z mnoˇziny a1 , a2 , . . . , an .

X. Poˇr´ adkové statistiky Na závˇer pop´ıˇseme dva algoritmy pro hled´ an´ı k-tého nejmenˇs´ıho prvku v dané podmnoˇzinˇe totálnˇe uspoˇrádaného univerza. Prvn´ı z nich vyuˇz´ıv´ a stejn´ y princip jako QUICKSORT. Nejprve zadáme pˇresné znˇen´ı naˇs´ı u ´lohy (´ uloha i algoritmy se daj´ı snadno pˇreformulovat pro pˇr´ıpad, kdy hledáme k−t´ y nejvˇetˇs´ı prvek). Pracujeme s totálnˇe uspoˇrádan´ ym univerzem U . Vstup: mnoˇzina prvk˚ u M = {a1 , a2 , . . . , an } ⊆ U a ˇc´ıslo i takové, ˇze 1 ≤ i ≤ n. V´ ystup: prvek ak takov´ y, ˇze |{j | 1 ≤ j ≤ n, aj ≤ ak }| = i. < n Kdyˇz i = 2 , pak ak se naz´ yvá medi´ an. FIND(M = (a1 , a2 , . . . , an ), i): zvol a ∈ M M1 := {b ∈ M | b < a}, M2 := {b ∈ M | b > a} if |M1 | > i − 1 then FIND(M1 , i) else if |M1 | < i − 1 then FIND(M2 , i − |M1 | − 1) else V´ ystup: a je hledan´ y prvek endif endif Korektnost:

D˚ ukaz korektnosti algoritmu je zaloˇzen na n´ asleduj´ıc´ım jednoduchém pozorován´ı: mˇejme mnoˇzinu M a prvek x a poloˇzme M1 = {m ∈ M | m < x}. Kdyˇz k ≤ |M1 |, pak k-t´ y nejmenˇs´ı prvek v M1 je stejn´ y jako k-t´ y nejmenˇs´ı prvek v M . Kdyˇz k > |M1 |, pak (k − |M1 |)-t´ y nejmenˇs´ı prvek v M \ M1 je k-t´ y nejmenˇs´ı prvek v M . Zb´ yv´ a vyˇsetˇrit sloˇzitost.

39 Časová složitost:

V nejhorˇs´ım pˇr´ıpadˇe voláme FIND n-kr´ at a jedno vol´ an´ı vyˇzaduje ˇcas O(|M |). Tedy ˇcasová sloˇzitost algoritmu FIND v nejhorˇs´ım pˇr´ıpadˇe je O(n2 ). Dobré volby prvku a mohou algoritmus znaˇcnˇe zrychlit. V tomto pˇr´ıpadˇe plat´ı stejn´ a diskuse jako pro QUICKSORT. Spoˇc´ıtáme oˇcekávan´ y ˇcas za pˇredpokladu, ˇze prvek a byl vybr´ an n´ ahodnˇe. Pak 1 pravdˇepodobnost, ˇze je k-t´ ym nejmenˇs´ım prvkem, je n , kde n = |M |. Oznaˇcme T (n, i) oˇcekávan´ y ˇcas algoritmu FIND pro nalezen´ı i-tého nejmenˇs´ıho prvku v n-prvkové mnoˇzinˇe M . Plat´ı i−1 n X 1 X T (n, i) = n + ( T (n − k, i − k) + T (k, i)), n k=1

k=i+1

protoˇze procedura FIND bez rekurzivn´ıho vol´ an´ı sebe sama vyˇzaduje ˇcas O(n). Pˇredpokládejme, ˇze T (m, i) ≤ 4m pro kaˇzdé m < n a kaˇzdé i takové, ˇze 1 ≤ i ≤ m. Pak T (n, i) =n +

i−1 n i−1 n X X 1 X 1 X ( T (n − k, i − k) + T (k, i)) ≤ n + ( 4(n − k) + 4k) = n n k=1

Indukční předpoklad

k=i+1

k=1

2

n+

k=i+1 2

4 n + 2ni − n − 2i 4 (2n − i)(i − 1) (n + i + 1)(n − i) ( + )=n+ ( ). n 2 2 n 2

V´ yraz v ˇcitateli zlomku nab´ yvá svého maxima pro i = 3 2 3n2 −2n n −n= . Tedy 2 2 T (n, i) ≤ n +

n 2

a jeho maximaln´ı hodnota je

4 3n2 − 2n ( ) = n + 3n − 2 = 4n − 2 < 4n. n 4

Protoˇze tento odhad plat´ı také pro n = 1 a n = 2, dok´ azali jsme indukc´ı, ˇze T (n, i) ≤ 4n pro vˇsechna n a vˇsechna i taková, ˇze 1 ≤ i ≤ n. Plat´ı tedy Vˇ eta. Algoritmus FIND nalezne i-t´ y nejmenˇs´ı prvek v n prvkové tot´ alnˇe uspoˇra ´dané mno2 ˇzinˇe a v nejhorˇs´ım pˇr´ıpadˇe vyˇzaduje ˇcas O(n ). Kdyˇz se pivot vol´ı n´ ahodnˇe nebo kdyˇz vˇsechny vstupn´ı mnoˇziny maj´ı stejnou pravdˇepodobnost, pak oˇcek´ avan´ y ˇcas je O(n). Neefektivní přirozený algoritmus:

Pro velmi malá i nebo pro i velmi bl´ızk´ a n pracuje rychleji pˇr´ım´ y pˇrirozen´ y algoritmus (udrˇzuje si posloupnost i nejmenˇs´ıch nebo n − i nejvˇetˇs´ıch prvk˚ u a k n´ı pˇrid´ avá dalˇs´ı tak, ˇze ten prvek, kter´ y pˇrekroˇcil danou hranici, je zapomenut). Tento algoritmus vˇsak nen´ı efektivn´ı pro obecná i.

Druhý algo.:

Následuj´ıc´ı algoritmus nalezne i-t´ y nejmenˇs´ı prvek v line´ arn´ım ˇcase i v nejhorˇs´ım pˇr´ıpadˇe. Vstupem je opˇet podmnoˇzina M tot´ alnˇe uspoˇr´ adaného univerza U a pˇrirozené ˇc´ıslo i takové, ˇze 1 ≤ i ≤ |M |. SELECT(M, i): n := |M | if n ≤ 100 then ˇ mnoˇzinu M , m := i-t´ setˇrid y nejmenˇs´ı prvek M else rozdˇel M do navzájem disjunktn´ıch pˇetiprvkov´ ych podmnoˇzin A1 , A2 , . . . , A⌈ n5 ⌉ (posledn´ı z podmnoˇzin m˚ uˇze m´ıt ménˇe neˇz 5 prvk˚ u).

40

for every j = 1, 2, . . . , ⌈ n5 ⌉ do najdi medián mj mnoˇziny Aj enddo n m ¯ :=SELECT({mj | j = 1, 2, . . . , ⌈ n5 ⌉}, ⌈ 10 ⌉) M1 := {m ∈ M | m < m}, ¯ M2 := {m ∈ M | m ¯ < m} if |M1 | > i − 1 then m :=SELECT(M1 , i) else if |M1 | < i − 1 then m :=SELECT(M2 , i − |M1 | − 1) else m := m ¯ endif endif V´ ystup: m endif D˚ ukaz korektnosti algoritmu je stejn´ y jako u algoritmu FIND. Zb´ yv´ a vyˇsetˇrit sloˇzitost. Nejprve dokáˇzeme následuj´ıc´ı lemma. Lemma. Kdyˇz n ≥ 100, pak |M1 |, |M2 | ≤

8n 11 .

D˚ ukaz. Pro j ≤ ⌊ n5 ⌋ plat´ı, ˇze kdyˇz mj < m, ¯ pak |Aj ∩ M1 | ≥ 3, kdyˇz mj > m, ¯ pak ¯ pak |Aj ∩ M1 | = |Aj ∩ M2 | = 2. Protoˇze |{j = 0, 1, . . . , ⌊ n5 ⌋ | |Aj ∩ M2 | ≥ 3, kdyˇz mj = m, n mj < m}|, ¯ |{j = 0, 1, . . . , ⌊ n5 ⌋ | mj > m}| ¯ ≥ ⌊ 10 ⌋, dost´ av´ ame, ˇze |M1 |, |M2 | ≥ ⌊ 3n 10 ⌋ − 1. 8n 3n 113n Dále plat´ı M1 ∩ M2 = ∅, M1 ∪ M2 = M \ {m} ¯ a protoˇze 11 + ⌊ 10 ⌋ − 1 ≥ 110 − 2 ≥ n kdyˇz n > 100, dostáváme poˇzadovan´ y odhad. Maximáln´ı ˇcas vyˇzadovan´ y algoritmem SELECT(M, i) pro |M | = n oznaˇcme T (n). Kdyˇz n ≤ 100, pak zˇrejmˇe existuje konstanta a takov´ a, ˇze T (n) ≤ an. Kdyˇz n > 100, pak ⌈ n5 ⌉ ≤ 21n ze SELECT(M, i) pro |M | > 100 bez rekurentn´ıch vol´ an´ı vyˇzaduje ˇcas O(|M |), 100 , a protoˇ 21n 8n plat´ı, ˇze T (n) ≤ T ( 100 ) + T ( 11 ) + bn pro nˇejakou konstantu b. Zvolme c ≥ max{a, 1100b 69 }. Ukáˇzeme, ˇze T (n) ≤ cn pro vˇsechna n. Kdyˇz n ≤ 100, tak tvrzen´ı zˇrejmˇe plat´ı, protoˇze 8n 69 a ≤ c. Kdyˇz n > 100, pak ⌈ 21n ze z volby c plyne b ≤ 1100 c, dostáváme 100 ⌉, ⌈ 11 ⌉ < n, a protoˇ T (n) ≤ c

21n 8n 1031c +c + bn = ( + b)n ≤ cn. 100 11 1100

Tedy Vˇ eta. Algoritmus SELECT nalezne i-t´ y nejmenˇs´ı prvek v line´ arn´ım ˇcase. Doporučení:

Algoritmus FIND je ve velké vˇetˇsinˇe pˇr´ıpad˚ u rychlejˇs´ı neˇz algoritmus SELECT, proto je v praxi doporuˇcován, i kdyˇz existuj´ı pˇr´ıpady (velmi ˇr´ıdké), kdy potˇrebuje kvadratick´ y ˇcas. Je známo, ˇze medián n-prvkové mnoˇziny lze nalézt s ménˇe neˇz 3n porovn´ an´ımi a ˇze kaˇzd´ y algoritmus hledaj´ıc´ı medián a pouˇz´ıvaj´ıc´ı porovn´ an´ı jako jedinou primitivn´ı operaci mezi prvky mnoˇziny vyˇzaduje v´ıce neˇz 2n porovn´ an´ı.

41

´ pr ˇehled Historicky Algoritmus HEAPSORT navrhl v roce 1964 Williams a vylepˇsil Floyd (rovnˇeˇz 1964). Návrh na pouˇzit´ı d-regulárn´ıch hald je folklor stejnˇe tak jako algoritmus MERGESORT. Algoritmy QUICKSORT a FIND zavedl Hoare (1962). Anal´ yza operace MERGE a hledán´ı optimáln´ıho stromu pocház´ı od Huffmana (1952) a line´ arn´ı implementaci algoritmu navrhl van Leeuwen (1976). Anal´ yza rozhodovac´ıch strom˚ u je folklor. Algoritmus HYBRIDSORT navrhli Meijer a Akl (1980), vylepˇsen´ a verze BUCKETSORTU (nazvaná WORDSORT) pocház´ı od Aho, Hopcrofta a Ullmana (1974). Algoritmus SELECT byl navrˇzen Blumem, Floydem, Prattem, Rivestem a Tarjanem (1972).

Datové struktury - haldy a třídicí algoritmy

Recommend Documents