====== IN18 Metody analýzy složitosti algoritmů ======
===== Zadání =====
(složitost v nejlepším, nejhorším, průměrném případu, očekávaná složitost)
===== Vypracování =====

==== Úvod ====

Složitost algoritmu vyjadřuje náročnost algoritmu na různé zdroje v průběhu výpočtu. Tyto zdroje potom určují tzv. //míry složitosti//, z nichž nejvýznamnější z hlediska informatiky jsou:
  * **časová** (určená časem výpočtu)
  * **prostorová** (určená požadavky na paměť v průběhu výpočtu)

Abychom mohli korektně zavést časovou i prostorovou složitost, je třeba nejprve porozumět pojmům //délka výpočtu// a //množství spotřebované paměti//.  

Přesné definice těchto pojmů závisí na výpočetním modelu -- např. Turingův stroj, RAM, funkcionální jazyk, while-program. Tyto modely jsou z hlediska vyjadřovací síly ekvivalentní (z hlediska výpočetní složitosti samozřejmě ne). Pro zavedení pojmu délka výpočtu budeme uvažovat funkcionální jazyk a imperativní jazyk zastoupený while-programem, abychom zdůraznili efekt referenční transparentnosti funkcionálního jazyka a stavového transformátoru jazyka imperativního.


==== Časová složitost ====

Při časové složitosti je důležité rozlišovat mezi dvěma pojmy:
  * časová složitost problému
  * časová složitost algoritmu (řešícího daný problém)

Platí: **časová složitost problému = časová složitost optimálního ("nejrychlejšího") algoritmu pro daný problém**

<box 95% round orange|Příklad problému a algoritmů, které problém řeší>**Problém:** Seřadit neseřazenou posloupnost přirozených čísel
**Algoritmy:** ''SelectSort'', ''QuickSort'', ''HeapSort'', ...
</box>

Časovou složitost problému mám zadefinovanou pomocí časové složitosti algoritmu. Tu si zadefinujeme pomocí funkce délky výpočtu algoritmu.

=== Délka výpočtu ===

Nechť <math>e</math> je výraz. **Délkou výpočtu výrazu **<math>e</math> rozumíme dobu nutnou pro pro vyhodnocení daného výrazu, a značíme ji <math>\tau(e)</math>. <math>\tau(e)</math> je rovna součtu délek vyhodnocení všech výrazů, které <math>e</math> obsahuje. Vyhodnocení elementárních aritmetických, logických, relačních operací nad skalárními operandy je konstantní. Proto i délku výpočtu výrazu, který obsahuje pouze jednoduché operace, považujeme za konstantní.

Délka vyhodnocování závisí také na vyhodnocovací strategii (viz [[home:inf:ap7|AP7, IN7 Vyhodnocování výrazů]]).

== Vyhodnocování funkce tau ==

  * <math>\tau(c)\ =\ 0 \quad</math> je-li <math>c</math> konstanta
  * <math>\tau(v)\ =\ 1 \quad</math> obsahuje-li výraz <math>v</math> zpřístupnění skalární hodnoty uložené v jedné přepisovatelné proměnné

  * <math>\tau(a\ \oplus\ b)\ =\ 1\ +\ \tau(a)\ +\ \tau(b) \quad</math>, kde <math>\oplus</math> je některý z primitivních binárních operátorů, které vyhodnocují oba své operandy (<math>+,\ -,\ mod,\ <,\ \ldots</math>)

  * <math>\tau(a\ \%26\%26\ b)\ =</math>
    * <math>1\ +\ \tau(a)\ +\ \tau(b) \quad</math> pro <math>a</math> pravdivé
    * <math>1\ +\ \tau(a) \quad</math> pro <math>a</math> nepravdivé

  * <math>\tau(if\ a\ then\ b\ else\ c)\ =</math>
    * <math>1\ +\ \tau(a)\ +\ \tau(b) \quad</math> pro <math>a</math> pravdivé
    * <math>1\ +\ \tau(a)\ +\ \tau(c) \quad</math> pro <math>a</math> nepravdivé

  * atd.((http://www.fi.muni.cz/~libor/vyuka/IB002/stud-materialy/slc-1.ps|Návrh algoritmů I -- Doplňující text k přednášce, str. 40-43))

Pro jazyky, které nejsou referenčně transparentní (např. imperativního paradigmatu) musí funkce <math>\tau</math> zohledňovat ještě stav před výpočtem výrazu <math>e</math> a změnu stavu po výpočtu. Funkce <math>\tau</math> pro jazyky, které nejsou referenčně transparentní, tak bude mít o jeden argument navíc, což bude stav výpočetního systému před výpočtem výrazu <math>e</math>, tedy předpis funkce bude vypadat <math>\tau(e, \sigma_x)</math>.

=== Časová složitost algoritmu ===

Víme, že délka výpočtu algortimu záleží od délky vstupu. Podle toho, o jaký případ se zajímáme (při dané délce vstupu), rozlišujeme:((https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II -- Slajdy z přednášek, str. 2))
  - **složitost v nejlepším případě**
    * skoro bezcenná informace
  - **složitost v nejhorším případě**
    * asi nejdůležitejší údaj
    * určuje **složitost algoritmu**
  - **složitost v průměrném případě**
    * někdy též označována jako **očekávaná složitost**
    * počítá se jako střední hodnota náhodné složitosti při nějakém rozložení vstupních dat
    * někdy může být i řádově lepší než složitost v nejhorším případě((http://www.beranr.webzdarma.cz/algoritmy/algoritmy.html|Algoritmy -- Radek Beran))
    * pro prakticke použití této složitost je rozhodující fakt, zda-li je málo pravděpodobné, že nastane nejhorší případ

Je-li //In// množina všech vstupních dat pro algoritmus //A//, pak pro <math>x\ \in In</math> zavedeme číslo <math>|x|\ \in\ \mathbb{N}</math>, které nazveme //velikost// vstupní hodnoty <math>x</math>. Časovou složitost zavedeme jako funkci <math>T_A\ :\ \mathbb{N}\ \rightarrow\ \mathbb{N}</math> takto:((http://www.fi.muni.cz/~libor/vyuka/IB002/stud-materialy/slc-1.ps|Návrh algoritmů I -- Doplňující text k přednášce, str. 56))

 <math>T_A(n)\ =\ max\{\tau(A)\ |\ |x|\ =\ n\}</math>\\

Pro jazyky, které nejsou referenčně transparentní označíme <math>\sigma_x</math> počáteční stav výpočtu, který odpovídá umístění hodnoty <math>x</math> na vstupu a funkci <math>T_A</math> zavedeme jako:\\

 <math>T_A(n)\ =\ max\{\tau(A,\ \sigma_x) |\ |x|\ =\ n\}</math>\\
 
**Časová složitost algoritmu** je tedy funkce, která pro každou velikost vstupních dat je rovná délce //nejdelšího výpočtu na všech možných datech této velikosti//, t.j. rovná se **složitosti v nejhorším případě**.

==== Rychlost růstu funkcí ====

Pro další práci s funkcí délky výpočtu výrazu a pojmem časová složitost algoritmu musíme umět porovnat časové složitosti dvou algoritmů. To uděláme tak, že porovnáme jejich délky výpočtů v závislosti na vstupu v nejhorším případě. Avšak nebudeme porovnávat algoritmy podle absolutní hodnoty délky výpočtu pro dané //n//; budeme se zajímat pouze a o //asymptotické// chování funkcí délky výpočtu.

=== Asymptotické chování funkcí ===

Neformálně: Jestli se zajímáme o //asymptotické chování// složitosti algoritmu, pak můžeme zanedbat všechny konstanty a jestli je funkce délky výpočtu ve tvaru součtu funkcí (např. polynom), vybereme pouze funkci která roste nejrychleji (např. vedoucí člen polynomu s koeficientem rovným 1).

=== Asymptotické porovnání rychlosti růstu funkcí ===

Definujeme následující množiny funkcí:

<box 95% round orange|Množiny funkcí sloužící k asymptotickému porovnání rychlosti růstu dvou funkcí>
<math>f,\ g:\ \mathbb{N} \rightarrow \mathbb{R}^+</math>
  * <math> f \in O(g)\ \Leftrightarrow\ \exists c, n_0 \in \mathbb{N}.\ \forall n \geq n_0.\ f(n) \leq c \cdot g(n)</math>
    * říkáme, že //f// roste (asymptoticky) nejvýše tak rychle jako //g//
  * <math> f \in \Omega(g)\ \Leftrightarrow\ \exists c, n_0 \in \mathbb{N}.\ \forall n \geq n_0.\ f(n) \geq \frac{1}{c} \cdot g(n)</math>
    * říkáme, že //f// roste (asymptoticky) aspoň tak rychle jako //g//
  * <math> f \in o(g)\ \Leftrightarrow\ \lim_{x\to\infty}\frac{f(x)}{g(x)}\ =\ 0</math>
    * říkáme, že //f// roste (asymptoticky) pomaleji než //g//
  * <math> f \in \omega(g)\ \Leftrightarrow\ \lim_{x\to\infty}\frac{f(x)}{g(x)}\ =\ \infty</math>
    * říkáme, že //f// roste (asymptoticky) rychleji než //g//
  * <math> f \in \Theta(g)\ \Leftrightarrow\ f \in O(g)\ \wedge\ f \in \Omega(g)</math>
    * říkáme, že //f// roste (asymptoticky) stějně rychle jak //g//
</box>

==== Analýza složitosti ====

Při analýze složitosti nás většinou zajímají tři druhy složitosti:((https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II -- Slajdy z přednášek, str. 3))
  * **horní odhad složitosti problému** = složitost konkrétního algoritmu
  * **dolní odhad složitosti problému**
    * Dokazuje se o hodně složitěji než horní odhad, protože musíme ukázat, že neexistuje žádný algoritmus, který by problém vyřešil s asymptoticky menší časovo složitostí
  * **složitost problému**

=== Dolní odhad složitosti problému - techniky ===

  * **Informační metoda** -- řešení problému v sobě obsahuje jisté množství informací a v každém kroku výpočtu jsme schopní určit jen část této informace (násobení matic, cesta v grafu, řazení)
  * **Redukce**
  * **Metoda sporu**
    * //Varianta A//: Za předpokladu, že algoritmus má složitost menší, než uvažovanou hranici, umíme zkonstruovat vstup, na kterém nedá korektní řešení.
    * //Varianta B//: Za předpokladu, že algoritmus najde vždy korektní řešení, umíme zkonstruovat vstup, pro který složitost výpočtu přesáhne uvažovanou hranici.((https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II -- Slajdy z přednášek, str. 4))


=== Způsoby výpočtu složitosti algoritmu ===

Pro určování časové složitosti algoritmu můžeme použít dva přístupy. Nechť //A// je algoritmus skládající se z kroků <math>I_1, \ldots, I_n</math>:((https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II -- Slajdy z přednášek, str. 19))

  * **Klasický přístup** -- Analyzujeme složitost každé operace. Výsledná složitost je součtem složitostí jednotlivých operací.
  * **Technika amortizace** -- Analyzujeme posloupnost jako celek. Tato technika umožňuje, na rozdíl od klasického přístupu mnohem přesnější určení časové složitosti algoritmu. Dává nám průměrnou dobu operace na nejhorších vstupních datech, tedy efektivně horní mez pro průměrnou složitost každé operace algoritmu. Používané metody:
    * //seskupení//
    * //účtů//
    * //potenciálových funkcí//

Poznamenejme, že amortizovaná složitost nepředstavuje další typ složitosti k dříve uvedeným (tj. nejlepší/nejhorší/průměrný případ), ale pouze **způsob** výpočtu složitosti.

==== Techniky výpočtu složitosti algoritmu pomocí amortizace ====

Jednotlivé techniky představíme na příkladě //zásobníku//.

<box 60% round green|Zásobník>
Operace:
  * ''Push(S, x)''
  * ''Pop(S)''
  * ''Multipop(S, k)'' -- vybere //k// prvků z S, resp. vyprázdní zásobník, je-li //|S| < k//.
</box>

=== Klasický přístup ===

<box 95% round orange|Zásobník -- příklad na zjištění složitosti klasickou metodou (neamortizovanou složitost)((https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II -- Slajdy z přednášek, str. 20))>
Uvažujeme posloupnost //n// operacím ''Pop, Push a Multipop''. ''Push'' a ''Pop'' mají složitosti 1. V posloupnosti //n// operací má ''Multipop'' v nejhorším případě složitost //n//. Proto celá posloupnost má **v nejhorším případě složitost** <math>n^2</math>.
</box>

=== Metoda seskupení ===

Operace rozdělíme do skupin a analyzujeme složitost celé skupiny operací současně.((https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II -- Slajdy z přednášek, str. 22))

<box 95% round orange|Zásobník -- příklad na zjištění amortizované složitosti **metodou seskupení**>
  - //Skupina 1// -- operace ''Push'', suma jejich složitostí nepřesáhne //n//
  - //Skupina 2// -- operace ''Pop'' a ''Multipop'', suma jejich složitostí (= počet prvků vybraných ze zásobníku) nemůže být větší než počet vykonaných operací ''Push'' (=počet prvků vložených do zásobníku). Složitost cele skupiny proto nepřesáhne //n//. 

Celá posloupnost ma v nejhorším případě složitost <math>2\cdot n</math>.
</box>

=== Metoda účtů ===

Každé **operaci přiřadíme kredit** (číslo), které může být různé od její skutečné ceny (složitosti). Při realizaci operace zaplatíme její cenu kredity podle těchto pravidel:((https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II -- Slajdy z přednášek, str. 24))

  * je-li **cena operace **<math>\leq</math>** kredit operace**, tak ze operaci zaplatíme tolik kreditů, jaká je její cena, zbytek kreditů uložíme na účet

  * je-li **cena operace **<math>></math>** kredit operace**, tak kredity potřebné pro zaplacení operace vezmeme z účtu.

Počátečný stav účtu je 0 kreditů. Jestli během celého výpočtu zůstane **počet kreditů na účtu nezáporný, pak součet kreditů vykonaných operací je **<math>\geq</math>** cena vykonaných operací**.

Platí: **Amortizovaná cena operace = počet kreditů přiřazených operaci**

  * VARIANTA: Kredity přiřadíme objektům datové struktury, nad kterou se operace realizují. Cena operace se zaplatí kredity objektů, se kterými operace manipuluje.

<note>Při důkazu složitosti algoritmu metodou účtů je velmi důležité zvolit si vhodnou kreditaci operací. Téměř vždy to rozhoduje o tom, jestli určíme složitost algoritmu správně.</note>


<box 95% round orange|Zásobník -- příklad na zjištění amortizované složitosti **metodou účtů**>
Zvolená kreditová funkce:

^   Operace    ^   Cena                     ^  Kredity  ^  
| ''Push''     |     1                      |     2     |
| ''Pop''      |     1                      |     0     |
| ''Multipop'' | <math>min\{k, |S|\}</math> |     0     |

<note>V okamžiku, když objekt vkládáme do zásobníku, "předplatíme" si tím jeho výběr</note>

Operaci ''Push'' zaplatíme 1 kreditem, 1 kredit dáme na účet. Operace ''Pop'' a ''Multipop'' zaplatíme kredity z účtu. Lehce dokážeme, že během celého výpočtu platí invariant **počet kreditů na účtě je rovný počtu prvků v zásobníku**. Z toho plyne, že zůstatek na účtě nikdy neklesne pod 0.

**Celková složitost** posloupnosti //n// operací je <math>\leq</math> součet kreditů vykonaných operací <math>\leq\ 2\cdot n</math>. 
</box>

=== Metoda potenciálové funkce ===

Operace se realizují na datovou strukturou. //Potenciálova funkce// <math>\Phi</math> přiřadí každé hodnotě (obsahu) datové struktury číslo. Uvažujme posloupnost //n// operací, nechť skutečná cena //i//-té operace v této posloupnosti je //c<sub>i</sub>//. Označme //D<sub>0</sub>// iniciální hodnotu datové struktury a //D<sub>i</sub>// její hodnotu po vykonání //i//-té operace.

Definujeme amortizovanou cenu //i//-té operace, <math>\hat{c}_i</math>, předpisem\\

<math>\hspace{4cm}\hat{c}_i\ {df \atop =}\ c_i\ +\ \Phi(D_i)\ -\ \Phi(D_{i-1})</math>

Součet amortizovaných cen operací je\\

<math>\sum_{i=1}^n \hat{c}_i\ =\ \sum_{i=1}^n\left(c_i\ +\ \Phi(D_i)\ -\ \Phi(D_{i-1})\right)\ =\ \sum_{i=1}^nc_i\ +\ \Phi(D_n)\ -\ \Phi(D_0)</math>

Za předpokladu, že <math>\Phi(D_n)\ \geq\ \Phi(D_0)</math> platí <math>\sum_{i=1}^n\ \hat{c}_i\ \geq\ \sum_{i=1}^n\ c_i</math>, t.j. **součet amortizovaných cen operací je horním odhadem pro složitost celé posloupnosti operací**.

Aby jsme zabezpečili platnost podmínky <math>\Phi(D_n)\ \geq\ \Phi(D_0)</math>, definujeme potenciálovou funkci tak, aby pro každou hodnotu //D// datové struktury platilo, že potenciál <math>\Phi(D)</math> je aspoň tak velký, jak potenciál počáteční hodnoty <math>D_0</math> datové struktury.((https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II -- Slajdy z přednášek, str. 28))


<box 95% round orange|Zásobník -- příklad na zjištění amortizované složitosti **metodou potenciálové funkce**>
Datová struktura je zásobník.
**Potenciálová funkce = počet prvků v zásobníku.**
Amortizovaná cena //i//-té operace -- rozlišujeme dle typu operace:

| ''Push''      | <math>\hat{c}_i\ =\ 1\ +\ (|S|\ +\ 1)\ -\ |S|\ =\ 2</math> |
| ''Pop''       | <math>\hat{c}_i\ =\ 1\ +\ |S|\ -\ (|S|\ +\ 1)\ =\ 0</math> |
| ''Multipop''  | <math>\hat{c}_i\ = \left\{\begin{array}{l l}
                                  k\ +\ (|S|\ -\ k)\ -\ |S|\ =\ 0 & \quad \mbox{je-li $|S| > k$}\\
                                  |S|\ +\ 0\ -\ |S|\ =\ 0 & \quad \mbox{je-li $|S| \leq k$}\\
                                \end{array} \right.</math> |
Pro všechny <math>1 \leq i \leq n</math> platí <math>\Phi(D_i) \geq \Phi(D_0)</math>.
Proto složitost celé posloupnosti je <math>\sum_{i=1}^n\ c_i\ \leq\ \sum_{i=1}^n\ \hat{c}_i\ \leq 2 \cdot n</math>
</box>

===== Předměty =====
  * [[https://is.muni.cz/auth/predmety/predmet.pl?fakulta=1433;obdobi=3084;kod=IB002|FI:IB002]] Návrh algoritmů I (jaro 2006), RNDr. Tomáš Pitner, Ph.D., RNDr. Libor Škarvada
  * [[https://is.muni.cz/auth/predmety/predmet.pl?fakulta=1433;obdobi=3524;kod=IB108|FI:IB108]] Návrh algoritmů II (jaro 2007), prof. RNDr. Ivana Černá, CSc., Mgr. Nikola Beneš

===== Použitá literatura =====
  * [[http://www.fi.muni.cz/~libor/vyuka/IB002/stud-materialy/slc-1.ps|Návrh algoritmů I -- Doplňující text k přednášce]]
  * [[https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II -- Slajdy z přednášek]]
  * [[http://www.beranr.webzdarma.cz/algoritmy/algoritmy.html|Algoritmy -- Radek Beran]]

===== Vypracoval =====

Shkodran Gerguri
Adam Libuša, 173122[AT]mail.muni.cz

Otázku si přečetl pan RNDr. Libor Škarvada a rámcově prošel. Jeho podněty pro doplnění textu, opravy nesrovnalostí a odstranění matoucích či k otázce se nevztahujících textů byly do otázky zaneseny. Tato kontrola je jen rámcová, stále se může stát, že v otázce zůstala zapomenutá chybka či nesrovnalost, vyučující za toto nenese odpovědnost, berte tuto rámcovou kontrolu jako formu pomoci od vyučujících pro studenty.

~~DISCUSSION~~