====== 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:** [[it_encyklopedie:algoritmus|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".

[[it_encyklopedie:algoritmus|Zpět na Algoritmy]]