Asymptotická složitost

Pro řešení jednoho zadaného problému můžeme použít různé algoritmy a zvolený postup řešení můžeme ještě různými způsoby naprogramovat. Dobrý programátor se liší od špatného kromě jiného tím, jak se staví k výběru algoritmu. Nespokojí se s prvním nápadem, jak by bylo možné danou úlohu řešit, ale porovnává různé postupy řešení a pečlivě z nich vybírá ten, který mu připadá nejvhodnější. Schopnost správné volby je jednou z klíčových dovedností každého dobrého programátora.¹

Když dva dělají totéž, není to totéž, to stejné platí i u algoritmů. Asymptotická složitost je užitečný nástroj, který nám pomáhá s vyběrem vhodného (efektivního, optimálního) algoritmu. Zajimá nás nejčastěji časová a paměťová složitost. Jde o dvě různá kriteria, která mohou jít i proti sobě. Často je totiž rychlost algoritmu vykoupená většími paměťovými nároky, protože ukládá mezivýsledky.

Jak meřit časovou komplexitu

Nároky na výpočetní prostředky, nebo paměť se u různých algoritmů mohou lišit řádově a současně se liší podle toho, jaký vstup náš program zrovna dostal.

Měřit časovou komplexitu algoritmus v sekundách běhu je nespolehlivé a prakticky nepoužitelné, protože na různém hardware se i jednotlivé instrukce programu vykonávají různě dlouho. Dokonce i na stejném počítači při různém vytížení operačního systému můžeme dostat při každém spuštění algoritmu zcela jiný výsledek.

Proto potřebujeme spolehlivější metodu pro porovnání kvalit algoritmů a tou je sledování chování algoritmu na velkých vstupních datech. Dobu výpočtu lze definovat jako počet všech elementárních operací (aritmetické operace, přiřazování, porovnávání apod.), které algoritmus vykoná při zpracování daného vstupu.

Jak meřit paměťovou komplexitu

Měříme ji v jednotkách velikosti paměti, tedy v bitech.

Porovnání algoritmů

Dobrou představu na to, kdy je časová složitost jednoho algoritmu lepší ve srovnání s druhým nám dává Landauova notace. Ke každému algoritmu lze jednoznačně přiřadit neklesající funkce, která udává dobu běhu daného algoritmu vzhledem k velikosti vstupních dat. Omezíme se zde na posloupnosti kladných reálných čísel, tedy funkce f: ℕ → ℝ⁺.

Asymptotická složitost používáme nikoliv k přesnému určení doby výpočtu, ale k jejímu řádovému odhadu, protože zanedbává multiplikativní a aditivní konstanty.

Díky této metodě můžeme algoritmy rozdělit do tříd složitosti (logaritmická, lineární, exponenciální, ...). Třídy složitosti pak můžeme vzájemně porovnávat následujícím vztahem

1 ≤ log(n) ≤ n ≤ n.log(n) ≤ n^k ≤ kⁿ ≤ n! ≤ nⁿ

Horní mez: Ο-notace

Ο notace je jeden z nejzákladnějších nástrojů k analýze časové a paměťové složitosti algoritmu. Řekneme, že funkce f(n) je asymptoticky menší nebo rovna než g(n), značíme f(n) ∈ Ο(g(n)), právě tehdy, když (∃c ∈ ℝ⁺)(∃n₀ ∈ ℕ⁺)(∀n ≥ n₀) 0 ≤ f(n) ≤ c.g(n)

Dolní mez: Ω-notace

Funkce f(n) je asymptoticky větší nebo rovna než g(n), značíme f(n) je Ω(g(n)), právě tehdy, když (∃c ∈ ℝ⁺)(∃n0 ∈ ℕ⁺)(∀n ≥ n₀) f(n) ≥ c.g(n) ≥ 0

Těsná mez: Θ-notace

Funkce f(n) je asymptoticky stejná jako g(n), značíme f(n) je Θ(g(n)), právě tehdy, když (∃c₁, c₂ ∈ ℝ⁺)(∃n₀ ∈ ℕ⁺)(∀n ≥ n₀) 0 ≤ c₁.g(n) ≤ f(n) ≤ c₂.g(n)

Matematicky skutečnost, že 2 funkce časové složitosti mají stejnou míru nárůstu hodnoty (složitosti), charakterizujeme tak, že jejich poměr (podíl) konverguje ke konečné nenulové hodnotě pro rostoucí argument n. Existují funkce, pro které nelze nalézt těsnou mez.

Striktní horní mez: ο-notace

DEFINICE:
f(n) ∈ ο(g(n)) ≝ (∀c ∈ ℝ⁺)(∃n₀ ∈ ℕ⁺)(∀n ≥ n₀) f(n) < c.g(n))

Mějme 2 algoritmy a nechť první má časovou složitost vyjádřenou funkcí f(n) a druhý g(n). Jestliže bude platit , pak funkce f(n) roste pomaleji než funkce g(n) a tudíž první algoritmus bude mít lepší časovou složitost.

Příklad $$\frac{1}{x} ∈ o(1)$$

Striktní dolní mez: ω-notace

DEFINICE:

f(n) ∈ ω(g(n)) ≝ (∀c ∈ ℝ⁺)(∃n₀ ∈ ℕ⁺)(∀n ≥ n₀: f(n) > c.g(n))

Opět limity určujeme, kdy je časová složitost algoritmu horší ve srovnání s druhým. Bude-li platit , bude mít lepší časovou složitost druhý algoritmus.

---

Složitost problému

Polynomická složitost

Pro daný problém P známe algoritmus, který ho řeší s časovou složitostí s(n), a zároveň umíme dokázat, že neexistuje algoritmus, který by problém P řešil s lepší časovou složitostí než s(n). Potom dává smysl říci, že složitost problému P je s(n).

Lineární složitost

Úlohy této třídy považujeme z časového hlediska za řešitelné. Jinak řešeno čas pro provedení algoritmů považujeme obecně za přijatelný.

Kvadratická složitost

Kvadratický polynom je pro větší počty údajů čas potřebný pro výpočet dosti citelný.

 

Exponenciální složitost

Exponenciální funkcí. Je zřejmé, že hodnota této funkce roste tak drasticky, že i pro poměrně malé počty údajů je potřeebný čas tak velký, že je nemožné takovými algoritmy provést výpočet. Tyto algoritmy patří do třídy algoritmů s nepolynomiální časovou složitostí. Mají tu vlastnost, že funkci jejich časové složitosti nelze shora ohraničit žádným polynomem. Algoritmy této třídy považujeme za neřešitelné přijatelném čase. Existuje řada praktických úloh, které vedou k algoritmům této třídy. Zejména sem patří úlohy na matematických grafech. V praxi se obchází sestavením algoritmu s přijatelnou (polynomickou) časovou složitostí pro tyto úlohy, které neřeší danou úlohu přesně, ale jen přibližně, čímž typicky dávají o něco horší výsledky, než by dal přesný algoritmus s nepolynomickou časovou složitostí.

 

Složitost řazení

Problémy třídění prvku, kam patří algoritmy třídění mají v nejlépším případě složitost n·log(n). To znamená, že existuje algoritmus schopný seřadit n prvků v čase O(n log n) a zároveň neexistuje asymptoticky rychlejší algoritmus.

Složitost grafů

V případě grafů obvykle vyjadřujeme složitost pomocí proměnných V a E, kde V je počet vrcholů grafu a E je počet jeho hran. I pro více proměnných vybíráme nejhorší případ.

---

K zamyslení

10⁸⁰ ∈ Θ(1)

log(n¹⁰⁰) ∈ Θ(log(n)), protože log(n¹⁰⁰) = 100log(n).

log₅(n) ∈ Θ(log(n)), log(n)/log₅(n).
Logaritmy o různých základech se liší pouze konstanta-krát a konstanty zanedbává.

Máme 2 algoritmy, jejichž časové složitosti jsou log_a(n),
Který z nich je rychlejší, tj. má přiznivější časovou složitost?

Vzhledem k tomu, že obě funkce časových složitostí neomezeně rostou, vede to k limitě výrazu typu +∞/+∞. Pro výpočet použijeme l’Hospitalovo pravidlo.
Dále pro logaritmus použijeme pravidlo, ješ logaritmus o základu a převádí na logaritmus o jiném základu b. log_a (n) = log_b (n)∗log_b (a)

Nyní již můžeme limitu počítat
$\lim\limits_{n \to \infty} \frac{log_2(n)}{\sqrt{n}} = \lim\limits_{n \to \infty} \frac{ \frac{1}{n}*ln(2) }{ \frac{1}{n}*n^{-\frac{1}{2}}} = 0$

Tedy první algoritmus má lepší časovou složitost a bude proto při výpočtu obecně rychlejší.

Pokud platí f(n) = O(g(n)), potom platí 2^f(n) = O(2^g(n))
Protipříklad f(n)=n, g(n)=2n

Pokud platí f(n) = o(g(n)), potom platí 2^f(n) = o(2^g(n))
Protipříklad f(n)=1/n, g(n)=1

Zdroje

[1] Algoritmy a programovací techniky, Pavel Töpfer 2007. 978-80-7196-350-9