Asymptotická složitost

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í „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 * 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 * 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²) se doba trvání průběhu zvyšuje kvadraticky, tedy pokud se zvýší délka vstupu 2krát, potřebný čas se zvýší 4krá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.

[editovat] Třídy složitosti

Algoritmy můžeme podle f(N) rozřadit do tříd.

Pokud je 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).

Některé asymptotické složitosti mají i své triviální pojmenování (jsou seřazeny od nejrychlejších k nejpomalejším):

• O(1) – konstantní
• O(log N) – logaritmická
• O(N) – lineární
• O(N log N) – lineárnělogaritmická
• O(N²) – kvadratická
• O(N³) – kubická
• obecně O(N^X) – polynomiální
• obecně O(X^N) – exponenciální
• O(N!) – faktoriálová

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

• O(1) indexování prvku v poli
• O(log₂ 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 reálných čísel podle velikosti (např. algoritmem Mergesort)
• O(N²) diskrétní Fourierova transformace (DFT)
• O(2^N) 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.

[editovat] Formální definice

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

právě tehdy když

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

Notace	Význam	Definice
	f je asymptoticky ohraničena funkcí g shora (až na konstantu)
	f je asymptoticky ohraničena funkcí g zdola (až na konstantu)
	f je asymptoticky ohraničena funkcí g z obou stran (až na konstantu)
	f je asymptoticky ohraničena funkcí g shora
	f je asymptoticky ohraničena funkcí g zdola
	asymptoticky rovné

[editovat] Vztahy mezi množinami

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

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(N²), 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=K^M (kde K je určeno tzv. radixem transformace 2,4,8,… a M je přirozené číslo), lze tento problém zjednodušit na složitost O(N log N).

[editovat] Amortizovaná časová složitost

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 nejhorší 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).

[editovat] Příklad výpočetní složitosti

Tento článek o algoritmu nebo datové struktuře je příliš stručný nebo neobsahuje důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte.