Asymptotická složitost

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Při řešení úloh pomocí výpočetní techniky musíme mít nástroj, kterým dokážeme porovnat efektivitu a rychlost vykonávání jednotlivých algoritmů. Pro tento účel byly zavedeny pojmy asymptotická složitost a operační náročnost algoritmu.

Asymptotická složitost je způsob klasifikace počítačových algoritmů. Určuje operační náročnost algoritmu tak, že zjišťuje jakým způsobem se bude chování algoritmu měnit v závislosti na změně velikosti (počtu) vstupních dat. Zapisuje se pomocí „Omikron notace“ („velké O notace“) jako O(f(N)) (např. O(N)). Obvykle se používá asymptotická časová a prostorová složitost.

Používaný zápis znamená, že náročnost algoritmu je menší než A + B \cdot f(N), kde A a B jsou vhodně zvolené konstanty a N je veličina popisující velikost vstupních dat. Zanedbáváme tedy multiplikativní i aditivní konstanty, tzn. O(N + 1000) = O(1000 \cdot N) = O(N). Zajímá nás jen chování funkce pro velké hodnoty N.

Například časová složitost O(N) (tzv. lineární) říká, že doba trvání práce algoritmu se zvýší přibližně tolikrát, kolikrát se zvýší velikost vstupu. Na druhou stranu u složitosti O(N^2) se doba trvání průběhu zvyšuje kvadraticky, tedy pokud se zvýší délka vstupu dvakrát, potřebný čas se zvýší čtyřikrát. U časové složitosti O(1) naopak na délce vstupu vůbec nezáleží a potřebný čas je stále stejný. Podobně je tomu i u prostorové složitosti, jen s tou změnou, že se jedná o potřebné paměťové (prostorové) nároky v závislosti na délce vstupních dat.

Třídy složitosti[editovat | editovat zdroj]

Algoritmy můžeme podle hodnot f(N) nějakého kritéria rozřadit do tříd. Kritéria jsou časová a paměťová složitost, dále pro paralelní a distribuované algoritmy komunikační složitost. Rozlišuje se složitost v nejhorším případě (která se odhaduje jednodušeji) a složitost v průměrném případě. Nejčastěji, tj. implicitně, se uvažuje o časové složitosti algoritmu v nejhorším případě. Dále lze určovat

Složitost problému je složitost nejlepšího algoritmu, který ho řeší. Každý konkrétní algoritmus poskytuje horní odhad složitosti.

Velikost dat N se obvykle měří v bitech, bytech anebo buňkách pevné velikosti (z hlediska asymptotické složitosti je rozdíl jen v multiplikativní konstantě), ale někdy se pro zjednodušení uvažuje jiné N. Například v grafových algoritmech se uvažuje graf o N vrcholech a takový graf může (a v některých případech musí) mít až N2 hran. Jiný příklad je čtvercová matice o straně N, která ve skutečnosti obsahuje až N2 položek.

V případě quicksortu je časová složitost v nejhorším případě O(N2) a v průměrném případě O(N log N). Algoritmus násobení čtvercových matic velikosti NxN podle definice má kubickou složitost O(N3), tj. problém násobení matic má složitost nejhůř kubickou. Strassenův algoritmus násobení matic má složitost přibližně O(N2,89) a jsou známy algoritmy s ještě lepší asymptotickou složitostí. Podobně diskrétní Fourierova transformace (DFT) počítaná přímočaře podle definice má složitost O(N2) a algoritmus rychlé Fourierovy transformace (FFT) má složitost O(N log N).

Časová složitost a třídy P a NP[editovat | editovat zdroj]

Pokud je časová složitost f(N) polynom, hovoříme o polynomiálně omezených algoritmech. Takové problémy, které řeší nějaký polynomiální algoritmus, patří do tzv. třídy P.

Pokud pro daný problém neexistuje polynomiálně omezený algoritmus, který řešení nalezne, ale existuje polynomiálně omezený algoritmus, který řešení ověří, hovoříme o nedeterministicky polynomiálních problémech. Problémy, které řeší nedeterministický algoritmus, patří do třídy NP (např. problém obchodního cestujícího, splnitelnost formule výrokové logiky a mnoho dalších).

Jednou z největších současných otevřených otázek teoretické informatiky je problém, zda se třídy P a NP rovnají. Vše nasvědčuje tomu, že to pravda není (viz NP-úplnost a problém P versus NP).

Typické příklady časové složitosti[editovat | editovat zdroj]

  • O(1) skok na prvek v poli dle indexu
  • O(log2 N) vyhledání prvku v seřazeném poli metodou půlení intervalu
  • O(N) vyhledání prvku v neseřazeném poli lineárním (sekvenčním) vyhledáváním
  • O(N log N) seřazení pole prvků s definovanou nerovností (např. reálná čísla podle velikosti, např. algoritmem Mergesort)
  • O(N2) diskrétní Fourierova transformace (DFT) počítaná přímočaře podle definice; sčítání dvou matic velikosti NxN
  • (aspoň) O(2N) přesné řešení problému obchodního cestujícího (či jiného NP-úplného problému hrubou silou)

Existují i funkce, u nichž nelze složitost vůbec shora rozumně omezit. Příkladem budiž Ackermannova funkce.

Seřazení tříd složitosti[editovat | editovat zdroj]

Některé asymptotické složitosti (v proměnné N s konstantou X) mají i své triviální pojmenování (jsou seřazeny od nejmenší k největší složitosti):

  • O(1) – konstantní
  • O(log log N) – dvojitě logaritmická
  • O(log N) – logaritmická
  • obecně O((log N){}^X), psáno také O(log{}^X N) - polylogaritmická
  • O(N{}^{1/2}) – odmocninová
  • O(N) – lineární
  • O(N log N) – lineárnělogaritmická
  • obecně O(N log{}^X N)
  • O(N^2) – kvadratická
  • O(N^3) – kubická
  • obecně O(N^X) – polynomiální
  • obecně O(X^N) – exponenciální
  • O(N!) – faktoriálová
  • superexponenciální: například O(2^{2^N})

Formální definice[editovat | editovat zdroj]

Nechť f(x) a g(x) jsou dvě funkce definované na nějaké podmnožině reálných čísel. Potom řekneme, že

f(x) \in \mathcal{O}(g(x))

právě tehdy když

\exists (C>0), x_0 : \forall(x>x_0) \; |f(x)| \leq |Cg(x)|

Další používané notace[editovat | editovat zdroj]

Notace Význam Definice
f(x) \in \mathcal{O}(g(x)) f je asymptoticky ohraničena funkcí g shora (až na konstantu) \exists (C>0), x_0 : \forall(x>x_0) \; |f(x)| \leq |Cg(x)|
f(x) \in \Omega(g(x)) f je asymptoticky ohraničena funkcí g zdola (až na konstantu) \exists (C>0), x_0 : \forall (x>x_0) \; |Cg(x)| \leq |f(x)|
f(x) \in \Theta(g(x)) f je asymptoticky ohraničena funkcí g z obou stran (až na konstantu) \exists (C,C'>0), x_0 : \forall (x>x_0) \; |Cg(x)| < |f(x)| < |C'g(x)|
f(x) \in o(g(x)) f je asymptoticky ohraničena funkcí g shora ostře \forall (C>0),\exists x_0 : \forall(x>x_0) \; |f(x)| < |Cg(x)|
f(x) \in \omega(g(x)) f je asymptoticky ohraničena funkcí g zdola ostře \forall (C>0),\exists x_0 : \forall(x>x_0) \; |Cg(x)| < |f(x)|
f(x)~\sim g(x) asymptoticky rovné \lim_{x \to \infty} \frac{f(x)}{g(x)} = 1

Vztahy mezi množinami[editovat | editovat zdroj]

\Theta(g(x)) = \mathcal{O}(g(x)) \cap \Omega(g(x))
\Theta(g(x)) = \mathcal{O}(g(x)) \smallsetminus o(g(x))
\Theta(g(x)) = \Omega(g(x)) \smallsetminus \omega(g(x))

Snižování výpočetní složitosti algoritmů[editovat | editovat zdroj]

Snahou programátorů je asymptotickou složitost dostat alespoň na polynomiální úroveň, horší složitosti jsou v reálných aplikacích (tedy u vyšších N) nepoužitelné. Typickým příkladem je diskrétní Fourierova transformace (DFT), která v obecném tvaru má asymptotickou složitost O(N2), proto je nevhodná pro transformaci vektorů větších délek. Existuje rychlá verze této transformace označovaná jako FFT (Fast Fourier Transform), která využívá skutečnosti, že pro délky vektorů N=KM (kde K je určeno tzv. radixem transformace 2,4,8,… a M je přirozené číslo), lze tento problém spočítat se složitostí O(N log N).

Pro opravdu velká data jsou často i nelineární algoritmy příliš náročné. Viz Big data.

Amortizovaná časová složitost[editovat | editovat zdroj]

Amortizovaná časová složitost je průměrný čas potřebný pro vykonání určité operace v sekvenci operací v nejhorším případě. Na rozdíl od časové složitosti v průměrném případě nevyužívá pravděpodobnosti. U amortizované složitosti je průměrný čas na operaci skutečně zaručený.

Tato metoda vyžaduje znalost toho, které sekvence operací jsou vůbec možné. Nejčastěji se to týká analýzy datových struktur, které si mezi jednotlivými operacemi udržují určitý stav. Některé datové struktury mají totiž takovou vnitřní organizaci, že na ní závisí složitost, a organizovanost dat se může během posloupnosti operací měnit. Základní myšlenka amortizované analýzy tkví v tom, že operace s velkou složitostí změní stav struktury tak, že tento nejhorší případ nemůže nastat po dlouhý čas, tudíž amortizuje svou cenu.

Jako jednoduchý příklad můžeme uvést specifickou implementaci dynamického pole, která zdvojnásobuje velikost pole pokaždé, když dojde k jeho naplnění. V tomto případě je tedy nutná realokace, v nejhorším případě tato operace potřebuje čas až O(N). Samotné vkládání prvků (bez nutnosti realokace) vyžaduje čas O(1), pro N prvků tedy také O(N). Pro vložení N prvků (včetně realokace) je tedy potřeba O(N) + O(N) = O(N), amortizovaný čas na jedno vložení prvku je pak O(N)/N = O(1).

Příklad výpočetní náročnosti[editovat | editovat zdroj]

Jedna operace zde trvá jednu nanosekundu.

Asymptotická složitost Velikost vstupních dat
10 20 50 100 1 000 1 000 000 1 000 000 000 1020
\log{\log{n}} 2 ns 3 ns 3 ns 3 ns 4 ns 5 ns 5 ns 7 ns
\log{n} 4 ns 5 ns 6 ns 7 ns 10 ns 20 ns 30 ns 67 ns
\sqrt{n} 4 ns 8 ns 8 ns 10 ns 32 ns 1 μs 32 μs 10 s
n 10 ns 20 ns 50 ns 100 ns 1 μs 1 ms 1 s 3 171 let
n\log{n} 34 ns 87 ns 283 ns 665 ns 10 μs 20 ms 30 s 210 675 let
n^2 100 ns 400 ns 3 μs 10 μs 1 ms 16 min 40 s 32 let
n^3 1 μs 8 μs 125 μs 1 ms 1 s 32 let
n^4 10 μs 160 μs 6 ms 100 ms 16 min 40 s
2^n 1 μs 1 ms 13 dní
3^n 59 μs 4 s 22 760 000 let
n! 4 ms 77 let
n^n 10 s

Nebezpečí používání asymptotické složitosti[editovat | editovat zdroj]

Multiplikativní konstanta nějakého algoritmu může být příliš velká (např. O(2^{100} N)) a tedy algoritmus prakticky nepoužitelný.

Podobný případ je, když asymptoticky lepší algoritmus A má větší multiplikativní konstantu než alg. A*, ale v důsledku toho je pro reálně používané, tj. dostatečně malé, velikosti dat výhodnější A*, protože A* má menší režii.

Externí odkazy[editovat | editovat zdroj]