Dolní odhady složitosti problémů

Definice (Složitost problému)

Složitost problému je složitost asymptoticky nelepšího \textbf{možného} algoritmu, který řeší daný problém (ne nejlepšího známého).

Každý konkrétní algoritmus dává horní odhad složitosti. Dolní odhady (až na triviální -- velikost vstupu, výstupu) jsou složitější.

Věta (Dolní odhad složitosti mediánu)

Pro výběr <math> k\,\!</math>-tého z <math> n\,\!</math> prvků je třeba alespoň <math> n-1\,\!</math> porovnání, tj. problém je <math> \Omega(n)\,\!</math>.

Důkaz

TODO

Věta (Dolní odhad složitosti třídění)

Pro každý třídící algoritmus, založený na porovnávání prvků, existuje vstupní posloupnost, pro kterou provede <math> \Omega(n\log n)\,\!</math> porovnání.

Důkaz

Nakreslím si rozhodovací strom jako model algoritmu -- všechny vnitřní uzly odpovídají nějakému porovnání, které algoritmus provedl, jejich synové jsou operace, které nasledovaly po různých výsledcích toho porovnání. Listy odpovídají setříděným posloupnostem. Aby byl algoritmus korektní, musí mít strom listy se všemi <math> n!\,\!</math> možnými pořadími prvků. Počet porovnání je výška stromu, proto stačí ukázat, že strom s <math> n!\,\!</math> listy má výšku <math> \Theta(n\log n)\,\!</math>.

Označím výšku jako <math> h\,\!</math>, pak počet listů je <math> \leq 2^h\,\!</math> a tedy <math> n!\leq 2^h\,\!</math>, tj. <math> h\geq \log n!\,\!</math>, stačí odhad faktoriálu jako <math> n^{\frac{n}{2}}\,\!</math>.

Amortizovaná složitost

Definice (Amortizovaná složitost)

Typicky se používá pro počítání časové složitosti operací nad datovými strukturami, počítá průměrný čas na 1 operaci při provedení posloupnosti operací. Dává realističtější odhad složitosti posloupnosti všech operací, než měření všech nejhorším případem.

Známe 3 metody amortizované analýzy (a používat budeme první dvě):

  • agregační

  • účetní

  • potenciálová (je podobná účetní, vynecháme)

Problémy:

  • Inkrementace binárního čítače -- do binárního čítače délky <math> k\,\!</math> postupně přičteme <math> n\,\!</math>-krát jedničku. Počet bitových operací na 1 přičtení je v nejhorším případě <math> O(\log n)\,\!</math>, ale amortizovaně dojdeme k <math> O(1)\,\!</math>.

  • Vkládání do dynamického pole -- začnu s prázdným polem délky <math> 1\,\!</math> a postupně vkládám <math> n\,\!</math> prvků. Pokud je stávající pole plné, alokujeme dvojnásobné a kopírujeme prvky. Počet kopírování prvků na jedno vložení je až <math> O(n)\,\!</math>, ale amortizovaně opět <math> O(1)\,\!</math>.

Algoritmus (Agregační metoda)

Postup: spočítáme nejhorší čas pro celou posloupnost <math> n\,\!</math> operací -- <math> T(n)\,\!</math>, amortizovaný čas na 1 operaci je pak <math> \frac{T(n)}{n}\,\!</math>.

  1. v průběhu <math> n\,\!</math> přičtení se <math> i\,\!</math>-tý bit překlopí <math> \lfloor \frac{n}{2^i}\rfloor\,\!</math>-krát, takže celková cena překlopení je <math> \leq n\cdot\sum_{i=0}^{\infty} \frac{1}{2^i} = 2n\,\!</math>, tj. amortizovaně na jedno přičtení <math> \frac{2n}{2} = \Theta(1)\,\!</math>

  2. cena <math> i\,\!</math>-tého vložení do pole je <math> c_i=\begin{cases}i \mbox{ pokud } \exists k:i-1 = 2^k\\ 1\mbox{ jinak}\end{cases}\,\!</math>. Celkem dostávám <math> T(n) = \sum_{i=1}^n c_i = n + \sum_{j=0}^{\lfloor \log n\rfloor} 2^j\leq n + 2n = 3n\,\!</math>, takže na jedno vložení vyjde <math> \frac{3n}{n} = \Theta(1)\,\!</math>.

Algoritmus (Účetní metoda)

Postup: Od každé operace vyberu urč. pevný "obnos", kterým onu operaci "zaplatím". Pokud něco zbyde, dám to na účet, pokud bude oprace naopak dražší než onen obnos, z účtu vybírám. Zůstatek na účtu musí být stále nezáporný -- pokud uspěji, obnos je amortizovaná cena 1 operace.

  1. Při každém přičtení je \underline{právě jeden} bit překlopen \underline{z 0 na 1}. Proto každému bitu zavedeme účet a za přičtení budeme vybírat 2 jednotky. Jedna je použita na překlopení daného bitu z 0 na 1 a druhá uložena na právě jeho účet; překlápění z 1 na 0 jsou hrazeny z účtů (protože každý bit, který má nastavenu 1 má na účtu právě 1 jednotku, projde to). Amortizovaná cena tedy vyjde <math> 2=\Theta(1)\,\!</math>.

  2. Od každého vložení vyberu 3 jednotky -- na vlastní vložení, na překopírování právě vloženého prvku při příštím vložení a na příští překopírování odpovídajícího prvku v levé polovině pole (na pozici <math> n-\frac{s}{2}\,\!</math>), který obnos ze svého vložení vyčerpal. Po expanzi je celkem na všech účtech <math> 0\,\!</math>, jindy víc, tj. amortizovaná cena operace je <math> 3=\Theta(1)\,\!</math>.

Binomiální a Fibonacciho haldy

Motivace

Složitost Dijkstrova algoritmu závisí na operacích EXTRACT-MIN a DECREASE-KEY nad datovou strukturou, v níž jsou uchovávany vrcholy podle vzdálenosti od zdroje (celkově se provádí n-krát EXTRACT-MIN a m-krát DECREASE-KEY). Chceme dosáhnout složitost <math> O(n\log n+m)\,\!</math>, tedy konstantní DECREASE-KEY a logaritmický EXTRACT-MIN.

Definice (Binomiální halda)

Binomiální strom <math> B_i\,\!</math> sestává z kořene a jeho dětí <math> B_0,B_1,\dots,B_{i-1}\,\!</math> (rekurzivně), navíc se zachovává vlastnost haldy. Řád uzlu je počet jeho synů, řád stromu řád jeho kořene.

Binomiální halda je soubor binomiálních stromů \underline{různých řádů}, doplněný o ukazatel MIN na strom s nejmenším kořenem. Implementovatelné např. v poli, kde <math> i\,\!</math>-tý prvek je buď ukazatel na strom řádu <math> i\,\!</math> nebo NIL.

Operace na binomiální haldě ("pilná" implementace):

  • MERGE -- slije dvě haldy podobně jako v binárním sčítání, jsou-li v obou haldách stromy řádu <math> i\,\!</math>, slepí je do jednoho stromu řádu <math> i+1\,\!</math> a přenáší dál. MIN nové haldy nastaví na menší z obou MIN. Složitost <math> O(\log n)\,\!</math>

  • EXTRACT-MIN -- utrhne kořen, jeho potomky prohlásí za další haldu a zmergeuje je s ostatními stromy. <math> O(\log n)\,\!</math>.

  • MAKEHEAP -- z jednoho prvku udělá haldu. <math> O(1)\,\!</math>.

  • INSERT -- kombinace MAKEHEAP a MERGE. Amortizovaně <math> O(1)\,\!</math> -- analogicky jako binární přičítání jedničky.

Operace v "líné" implementaci: povolím (dočasnou) existenci více stromů stejného řádu, navíc místo pole stromů použiji kruhový spoják.

  • MERGE -- je proste napojení spojáků za sebe. <math> O(1)\,\!</math>.

  • INSERT -- to samé, ale volá líný MERGE, takže je <math> O(1)\,\!</math>.

  • EXTRACT-MIN -- oddělí minimum, do spojáku zavede všechny syny minima, to je <math> O(\log n)\,\!</math>. Pak provede KONSOLIDACE -- upraví haldu do podoby, kdy je každý řád zastoupen nejvýše jedním stromem. To běží taky v <math> O(\log n)\,\!</math>:

Stromy, které prodělají konsolidaci, rozdělím na dvě skupiny:

  • Ty, co zaniknou (jsou slité pod jiným uzlem) zaplatí z účtu svého kořene: za odstranění ze spojáku a přepojení do stromu jde o konst. práci.

  • Za ty, co nezaniknou (jejich kořeny zůstávají kořeny i po konsolidaci) zaplatí EXTRACT-MIN, což jde, protože jich je logaritmicky.

Definice (Fibonacciho halda)

Je stejná jako Binomiální s línou implementací, navíc ale povolím i jiné než binomiální stromy; řád stromu je pořád definován stejně, slévám stále pouze stromy stejného řádu. Stromy mají stále exponenciálně uzlů vzhledem k řádu (důkaz viz níže).

  • MERGE, INSERT, EXTRACT-MIN -- implementovány stejně jako u binomiálních, mám navíc:

  • DECREASE-KEY -- sníží klíč <math> i\,\!</math> o <math> \delta\,\!</math>, pak podstrom s <math> i\,\!</math> jako kořenem odřízne a zavede do spojáku jako samostatný strom. Od každého vrcholu <math> x\,\!</math> můžou být odříznuti max. dva synové, tj. pokud odřezávám druhého, odříznu hned po něm i <math> x\,\!</math>. Pracuje amortizovaně v <math> O(1)\,\!</math>, i když může jedna operace trvat až <math> O(\log n)\,\!</math>.

K prvkům se musím dostat v konstantním čase. Každé odříznutí platí 4 jednotky -- jednu za vlastní práci, jednu na účet nového kořene a dvě na účet otce -- když jsou otci odříznuti 2 synové, má na zaplacení svého odříznutí.

Lemma (Minimální řád vrcholu ve Fibonacciho haldě)

Nechť <math> x\,\!</math> je nějaký vrchol a <math> y_1,\dots,y_m\,\!</math> jsou jeho synové v pořadí podle slití. Pak <math> \forall i\in\{1,\dots,N\}\,\!</math> je řád <math> y_i\,\!</math> aspoň <math> i-2\,\!</math>.

Důkaz

V okamiku, kdy <math> y_i\,\!</math> byl "slit" pod <math> x\,\!</math>, byl řád <math> x\,\!</math> aspoň <math> i-1\,\!</math> (protože všichni synové s menším indexem byli na <math> x\,\!</math> už přidáni) a řád <math> y_i\,\!</math> taktéž (slévám jen stromy stejného řádu), navíc <math> y_i\,\!</math> mohl být odříznut jen 1 syn, jinak by byl odříznutý sám.

Věta (O počtu vrcholů ve Fibonacciho stromech)

Strom řádu <math> i\,\!</math> ve Fibonacciho haldě má velikost alespoň <math> \varphi^i\,\!</math> pro nějaké <math> \varphi > 1\,\!</math>.

Důkaz

<math> F_i\,\!</math> nechť je nejmenší možný Fibonacciho strom řádu <math> i\,\!</math>, splňující omezení na odřezávání, počet jeho vrcholů buď <math> f_i\,\!</math> (odpovídá Fibonacciho posloupnosti). <math> F_i\,\!</math> musí vzniknout "slitím" <math> F_{i-1}\,\!</math> a <math> F_{i-2}\,\!</math> (z omezení na řád vrcholu v lemmatu). To skutečně jde dostat posloupností operací -- mám 2x <math> F_i\,\!</math> (z indukce <math> F_{i-2} \cup F_{i-3}\,\!</math>) a <math> F_0\,\!</math> (dummy s nejmenším klíčem), zahodím <math> F_0\,\!</math> v extract-min a výsledná konsolidace mi dá <math> F_i\,\!</math> ze dvou <math> F_{i-1}\,\!</math>. Následně provedu DECREASE-KEY na kořen jednoho z <math> F_{i-3}\,\!</math> a tím mám <math> F_i\,\!</math> jako spojení <math> F_{i-1}\,\!</math> a <math> F_{i-2}\,\!</math>. Dostávám tedy rekurentní vzorec <math> f_i = f_{i-1} + f_{i-2}\,\!</math> a jako u Fibonacciho čísel vyčíslím <math> \varphi = \frac{1+\sqrt{5}}{2}\,\!</math>.