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

Diskuze

MIchal Bednář, 2008/06/20 19:28

co se ucite k teto otazce? co je ocekavana a prumerna slozitost? Prumerna je asi amortizovana, ne? Moc nevim, co si k teto otazce pripravit. Napada me ukazat na nejakym vhodnym prikladu jednotlive slozitosti a tim to asi konci. Mozna jeste zminit slozitostni tridy (podobne jak to je v otazce Slozitost).

Shkodran Gerguri, 2008/06/20 19:59

Ono je tam toho vic. Napr. metoda uctu, metoda potencialove funkce - to vse se pouziva pri amortizovane slozitosti.

Adam Libuša, 2008/06/20 19:30

Ja to teda skúsim vypracovať…

Shkodran Gerguri, 2008/06/20 20:00

Diky.

Michal Bednář, 2008/06/20 20:15

sorry..obnovil jsem stranku a vlozilo se mi to tam znovu. Jinak dik vsem, kdo pracuji na vypracovani teto otazky.

Shkodran Gerguri, 2008/06/21 21:54

Tak jsem to prosel, a zda se mi, ze tam nic nechybi.

Adam Libuša, 2008/06/21 22:08

Ok, díky, teraz ešte keby sa na to pozrel nejaký vyučujúci..

Shkodran Gerguri, 2008/06/21 22:43

Ok, zkusim napsat Dr. Skarvadovi, prof. Cerne bych radeji nepsal, aby si to nevylozila nejak zle.

Adam Libuša, 2008/06/21 22:58

Tak ako nie je to od slova do slova prepísané z jej materiálov, ale niečo na tom asi bude :)

Shkodran Gerguri, 2008/06/21 23:02

Takhle jsem to nemyslel :), spis jde o to, aby ji ta zadost neprisla moc troufala. Kazdopadne jsem uz napsal Dr. Skarvadovi, tak snad se na to podiva.

Dusan Katona, 2008/06/22 10:49

Otazka je vypracovana pekne, diki :) Mam len jednu pripomienku:
Podla mna zlozitost v priemernom pripade sa nerovna ocakavanej zlozitosti -
1)pride mi to nelogicke preco by do zadania davali 2 terminy, ktore znamenaju to iste
2)myslim si, ze ocakavana zlozitost je nieco ako kolko platnych vystupov ocakavame, tak podla toho sa urci zlozitost - vid Karp-Rabinov alg., kde ocakavana zlozitost je O((n-m+1) + cm), kde c je pocet platnych posunov. Na druhu stranu, zlozitost v priemernom pripade Karp-Rabinovho alg. neviem ako by sa urcovala :)

Adam Libuša, 2008/06/22 13:38

Diky, snažil som sa :) Nikde som v skriptách nemohol násť definíciu očakávanej zložitosti, tak som čerpal odtiaľto. Tie dve rôzne podotázky - ja viem, tiež ma to napadlo, ale tak som si povedal prečo nie, chceli možno povedať, že to je to isté. Alebo sa možno len rôznia termíny z rôzných zdrojov.

Na druhú stranu ak zoberiem ten pojem z Karp-Rabinovho algoritmu “ nieco ako kolko platnych vystupov ocakavame, tak podla toho sa urci zlozitost“, tak sa mi to zdá dosť podobné tomuto: „počítá se jako střední hodnota náhodné složitosti při nějakém rozložení vstupních dat“ :). Každopádne ak nájdeš niekde nejakú lepšiu definíciu očakávanej zložitosti, kľudne to tam prepíš.

You could leave a comment if you were logged in.

home/inf/in18.txt · Poslední úprava: 2020/04/12 16:56 (upraveno mimo DokuWiki)

Nahoru