Asymptotická složitost

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á

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é.

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

Počet prvků vstupních dat	Asymptotická složitost
	O(1)	O(N)	O(N log N)	O(N2)	O(N3)	O(2N)
1	1	1	1	1	1	2
10	1	10	10	100	1000	1024
100	1	100	200	10000	1000000	1030
1000	1	1000	3000	1000000	109	10300
1000000	1	1000000	6000000	1012	1018	103000