Obsah

IN18 Metody analýzy složitosti algoritmů
Diskuze

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

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, …

Č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ť $e$ je výraz. Délkou výpočtu výrazu $e$ rozumíme dobu nutnou pro pro vyhodnocení daného výrazu, a značíme ji $\tau(e)$ . $\tau(e)$ je rovna součtu délek vyhodnocení všech výrazů, které $e$ 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 AP7, IN7 Vyhodnocování výrazů).

Vyhodnocování funkce tau

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

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

$\tau(a\ \%26\%26\ b)\ =$
- $1\ +\ \tau(a)\ +\ \tau(b) \quad$ pro $a$ pravdivé
- $1\ +\ \tau(a) \quad$ pro $a$ nepravdivé

$\tau(if\ a\ then\ b\ else\ c)\ =$
- $1\ +\ \tau(a)\ +\ \tau(b) \quad$ pro $a$ pravdivé
- $1\ +\ \tau(a)\ +\ \tau(c) \quad$ pro $a$ nepravdivé

atd.¹⁾

Pro jazyky, které nejsou referenčně transparentní (např. imperativního paradigmatu) musí funkce $\tau$ zohledňovat ještě stav před výpočtem výrazu $e$ a změnu stavu po výpočtu. Funkce $\tau$ 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 $e$ , tedy předpis funkce bude vypadat $\tau(e, \sigma_x)$ .

Č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:²⁾

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ě³⁾
- 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 $x\ \in In$ zavedeme číslo $|x|\ \in\ \mathbb{N}$ , které nazveme velikost vstupní hodnoty $x$ . Časovou složitost zavedeme jako funkci $T_A\ :\ \mathbb{N}\ \rightarrow\ \mathbb{N}$ takto:⁴⁾

$T_A(n)\ =\ max\{\tau(A)\ |\ |x|\ =\ n\}$

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

$T_A(n)\ =\ max\{\tau(A,\ \sigma_x) |\ |x|\ =\ n\}$

Č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í:

Množiny funkcí sloužící k asymptotickému porovnání rychlosti růstu dvou funkcí

$f,\ g:\ \mathbb{N} \rightarrow \mathbb{R}^+$

$f \in O(g)\ \Leftrightarrow\ \exists c, n_0 \in \mathbb{N}.\ \forall n \geq n_0.\ f(n) \leq c \cdot g(n)$
- říkáme, že f roste (asymptoticky) nejvýše tak rychle jako g
$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)$
- říkáme, že f roste (asymptoticky) aspoň tak rychle jako g
$f \in o(g)\ \Leftrightarrow\ \lim_{x\to\infty}\frac{f(x)}{g(x)}\ =\ 0$
- říkáme, že f roste (asymptoticky) pomaleji než g
$f \in \omega(g)\ \Leftrightarrow\ \lim_{x\to\infty}\frac{f(x)}{g(x)}\ =\ \infty$
- říkáme, že f roste (asymptoticky) rychleji než g
$f \in \Theta(g)\ \Leftrightarrow\ f \in O(g)\ \wedge\ f \in \Omega(g)$
- říkáme, že f roste (asymptoticky) stějně rychle jak g

Analýza složitosti

Při analýze složitosti nás většinou zajímají tři druhy složitosti:⁵⁾

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.⁶⁾

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ů $I_1, \ldots, I_n$ :⁷⁾

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.

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.

Klasický přístup

Zásobník – příklad na zjištění složitosti klasickou metodou (neamortizovanou složitost)⁸⁾

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 $n^2$ .

Metoda seskupení

Operace rozdělíme do skupin a analyzujeme složitost celé skupiny operací současně.⁹⁾

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 $2\cdot n$ .

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:¹⁰⁾

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

je-li cena operace $>$ 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 $\geq$ 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.

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ě.

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`	$min\{k, \|S\|\}$	0

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

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 $\leq$ součet kreditů vykonaných operací $\leq\ 2\cdot n$ .

Metoda potenciálové funkce

Operace se realizují na datovou strukturou. Potenciálova funkce $\Phi$ 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_i. Označme D₀ iniciální hodnotu datové struktury a D_i její hodnotu po vykonání i-té operace.

Definujeme amortizovanou cenu i-té operace, $\hat{c}_i$ , předpisem

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

Součet amortizovaných cen operací je

$\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)$

Za předpokladu, že $\Phi(D_n)\ \geq\ \Phi(D_0)$ platí $\sum_{i=1}^n\ \hat{c}_i\ \geq\ \sum_{i=1}^n\ c_i$ , 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 $\Phi(D_n)\ \geq\ \Phi(D_0)$ , definujeme potenciálovou funkci tak, aby pro každou hodnotu D datové struktury platilo, že potenciál $\Phi(D)$ je aspoň tak velký, jak potenciál počáteční hodnoty $D_0$ datové struktury.¹¹⁾

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`	$\hat{c}_i\ =\ 1\ +\ (\|S\|\ +\ 1)\ -\ \|S\|\ =\ 2$
`Pop`	$\hat{c}_i\ =\ 1\ +\ \|S\|\ -\ (\|S\|\ +\ 1)\ =\ 0$
`Multipop`	$\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.$

Pro všechny $1 \leq i \leq n$ platí $\Phi(D_i) \geq \Phi(D_0)$ .
Proto složitost celé posloupnosti je $\sum_{i=1}^n\ c_i\ \leq\ \sum_{i=1}^n\ \hat{c}_i\ \leq 2 \cdot n$

Předměty

FI:IB002 Návrh algoritmů I (jaro 2006), RNDr. Tomáš Pitner, Ph.D., RNDr. Libor Škarvada
FI:IB108 Návrh algoritmů II (jaro 2007), prof. RNDr. Ivana Černá, CSc., Mgr. Nikola Beneš

Použitá literatura

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.

¹⁾

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

²⁾

https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II – Slajdy z přednášek, str. 2

³⁾

http://www.beranr.webzdarma.cz/algoritmy/algoritmy.html|Algoritmy – Radek Beran

⁴⁾

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

⁵⁾

https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II – Slajdy z přednášek, str. 3

⁶⁾

https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II – Slajdy z přednášek, str. 4

⁷⁾

https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II – Slajdy z přednášek, str. 19

⁸⁾

https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II – Slajdy z přednášek, str. 20

⁹⁾

https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II – Slajdy z přednášek, str. 22

¹⁰⁾

https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II – Slajdy z přednášek, str. 24

¹¹⁾

https://is.muni.cz/auth/el/1433/jaro2007/IB108/um/slajdy.pdf|Návrh algoritmů II – Slajdy z přednášek, str. 28