{{TOC float}}
{{Sources|
''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 nejlepšího ''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|}}
Intuitivně potřebuju medián, i kdyby mi spadnul z nebe, porovnat se všemi ostatními prvky, abych vůbec zjistil, jestli to je medián ...
====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ů.
Pro plýtvající algoritmus mohou existovat listy, neodpovídající žádné permutaci, tj. porovnává stejnou dvojici prvků dvakrát (a jedna z možností už nemůže nastat). Pro rovnoměrné rozdělení je očekávaný čas průměrná délka cesty od kořene k listům, nejhorší čas je výška stromu.
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>, pro dolní odhad <math>\Omega(n\log n)</math> stačí odhad faktoriálu <math> n! < n^{\frac{n}{2}}\,\!</math>, případně můžu použít Stirlingův vzorec <math> n!\approx \sqrt{2\pi n}(\frac{n}{e})^n\,\!</math> a dostávám <math>\Theta(n\log n)</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}{n} = \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 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>
{{Statnice I3}}
