Big O notace (Asymptotická složitost)

Big O notace je jazyk, který programátoři používají k porovnávání efektivity algoritmů. Zaměřuje se na „nejhorší možný scénář“ (Worst Case). Pomáhá nám odpovědět na otázku: „Pokud se množství dat zdvojnásobí, zpomalí se program dvakrát, čtyřikrát, nebo vůbec?“

1. Nejběžnější typy složitosti

Zde jsou seřazeny od nejrychlejších po nejpomalejší:

O(1) – Konstantní složitost

Doba běhu je stále stejná, bez ohledu na to, jak velká jsou data.

Příklad: Přístup k prvku v poli pomocí indexu (vím přesně, kde je).

Vnímání: Extrémně rychlé.

O(log n) – Logaritmická složitost

Doba běhu roste velmi pomalu. Typické pro algoritmy, které při každém kroku rozdělí data na polovinu.

Příklad: Binární vyhledávání v seřazeném seznamu.

Vnímání: Velmi efektivní (i pro miliardy prvků stačí pár desítek kroků).

O(n) – Lineární složitost

Doba běhu roste přímo úměrně s počtem prvků.

Příklad: Prohledávání neseřazeného seznamu (musím se podívat na každý prvek).

Vnímání: Férové, běžné u jednoduchých operací.

O(n log n) – Linearitmetická složitost

O něco pomalejší než lineární, ale stále velmi dobrá.

Příklad: Efektivní třídicí algoritmy jako MergeSort nebo QuickSort.

Vnímání: Standard pro zpracování velkých dat.

O(n²) – Kvadratická složitost

Doba běhu roste se čtvercem velikosti dat. Pokud se data zdvojnásobí, čas vzroste čtyřikrát.

Příklad: Dva vnořené cykly (každý prvek porovnávám s každým jiným).

Vnímání: Pomalé. Pro velké objemy dat (např. miliony záznamů) nepoužitelné.

2. Praktické srovnání

Představte si, že jedna operace trvá 1 milisekundu ($1\text{ ms}$). Jak dlouho bude trvat zpracování $n = 1000$ prvků?

Notace	Počet operací	Čas
$O(1)$	1	$1\text{ ms}$
$O(\log n)$	~10	$10\text{ ms}$
$O(n)$	1 000	$1\text{ s}$
$O(n \log n)$	~10 000	$10\text{ s}$
$O(n	2)$	1 000 000	$16.6\text{ min}$
$O(2	n)$	$2	{1000}$	Více než věk vesmíru

3. Proč ignorujeme konstanty?

V Big O notaci nás nezajímají drobné detaily. Algoritmus, který provede $2n$ operací, je stále považován za O(n). Stejně tak $n + 100$ je stále O(n). V měřítku miliard prvků jsou tyto konstanty nepodstatné – rozhodující je „tvar“ křivky růstu.

4. Časová vs. Prostorová složitost

Časová (Time Complexity): Jak dlouho to trvá.

Prostorová (Space Complexity): Kolik paměti (RAM) algoritmus potřebuje během svého běhu. Často musíme dělat kompromis: buď je algoritmus rychlý a žere moc paměti, nebo je úsporný, ale pomalý.

Zlaté pravidlo: Při programování se vždy snažte vyhnout složitostem jako $O(n^2)$ a horším, pokud víte, že váš systém bude zpracovávat velká data. Rozdíl mezi $O(n \log n)$ a $O(n^2)$ je rozdílem mezi fungující aplikací a systémem, který „zamrzne“.

Zpět na Algoritmy