Syntax highlighting of Archiv/Státnice - Odhady složitosti

{{TOC float}}

''Tohle je poněkud obšírnější výcuc ke [[Státnice|státnicovým okruhům]] ze [[Státnice_-_Informatika_-_Složitost_(obory_Matematická_lingvistika_a_Softwarové_systémy)|složitosti]] pro obory [[Státnice_-_Informatika_-_I3:_Matematická_lingvistika|Matematická lingvistika]] a [[Státnice_-_Informatika_-_I2:_Softwarové_systémy|Softwarové systémy]], pocházející ze zápisků z předmětu [[Složitost I]] -- [[User:Tuetschek|Tuetschek]] 22:44, 16 Aug 2010 (CEST)''
==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í (BÚNO jsou-li prvky různé, bude strom binární). 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:  
* [[#Algoritmus (Agregační metoda)|agregační]]
* [[#Algoritmus (Účetní metoda)|účetní]]
* [[#Algoritmus (Potenciálová metoda)|potenciálová]]

====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)====

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>.  
* '''Binární sčítání''': 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> 
* '''Vkládání''': 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)====

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.  
* '''Binární sčítání''': Při každém přičtení je ''právě jeden'' bit překlopen ''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>. 
* '''Vkládání''': 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>.

====Algoritmus (Potenciálová metoda)====

Je to podobné bankovní, roli účtu hraje nějaká funkce <math> w\,\!</math>, která popisuje vhodnost jednotlivých konfigurací <math> D_0,D_1,\dots\,\!</math>. Potřebuji potom, aby <math>w(D_i) \geq w(D_0)\ \forall i\,\!</math>. Amortizovaná složitost <math>i\,\;</math>-té operace <math> o\,\!</math> je potom:
:<math> am(o_i)=T(o_i)+w(D_{i+1})-w(D_i)\,\!</math>. 

Složitost nejhoršího případu celé posloupnosti operací může být mnohem "rychlejší" než posloupnost nejhorších případů jednotlivých operací:
:<math>\sum_{i=1}^n T(o_i)\leq\sum_{i=1}^n am(o_i)+w(D_0)\,\!</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>.