Asymptotická složitost

Z Wikipedie, otevřené encyklopedie

Asymptotická složitost je způsob klasifikace počítačových algoritmů. Urč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“ (např. O(N)). Obvykle se používá asymptotická časová a prostorová složitost.

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 2-krát, potřebný čas se zvýší 4-krá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.

Asymptotická složitost zanedbává jakékoli konstanty, tzn. O(N + 1000) = O(1000 * N) = O(N). Některé asymtotické 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 2$ ) - kvadratická
O( $N 3$ ) - kubická
obecně O( $N X$ ) - polynomiální
obecně O( $X N$ ) - exponenciální
O(N!) - faktoriálová

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

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] Příklad výpočetní složitosti

Počet prvků vstupních dat	Asymptotická složitost
Počet prvků vstupních dat	O(1)	O(N)	O(N log N)	O(N²)	O(N³)	O(2^N)
1	1	1	1	1	1	2
10	1	10	10	100	1000	1024
100	1	100	200	10000	1000000	10³⁰
1000	1	1000	3000	1000000	10⁹	10³⁰⁰
1000000	1	1000000	6000000	10¹²	10¹⁸	10³⁰⁰⁰