Asymptotická složitost: Porovnání verzí

Při řešení úloh pomocí [[Výpočetní technika|výpočetní techniky]] musíme mít nástroj, kterým dokážeme porovnat [[Efektivnost algoritmu|efektivitu]] a rychlost vykonávání jednotlivých [[Algoritmus|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 [[algoritmus|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 ([[Operace (matematika)|počtu]]) vstupních [[Data|dat]]. Zapisuje se pomocí [[Landauova notace|Landauovy notace]] (též „Omikron notace“, nebo „velké O notace“) jako <math>O(f(N))</math> (např. <math>O(N)</math>). Obvykle se používá asymptotická časová a prostorová složitost.

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

Například časová složitost <math>O(N)</math> (tzv. lineární) říká, že [[Čas|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 <math>O(N^2)</math> 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 <math>O(1)</math> 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.

Velikost dat <math>N</math> se obvykle měří v [[Bit|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é <math>N</math>. Například v grafových algoritmech se uvažuje graf o <math>N</math> vrcholech a takový graf může (a v některých případech musí) mít až <math>N^2</math> hran. Jiný příklad je [[čtvercová matice]] o straně <math>N</math>, která ve skutečnosti obsahuje až <math>N^2</math> položek.