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?“
Zde jsou seřazeny od nejrychlejších po nejpomalejší:
Doba běhu je stále stejná, bez ohledu na to, jak velká jsou data.
Doba běhu roste velmi pomalu. Typické pro algoritmy, které při každém kroku rozdělí data na polovinu.
Doba běhu roste přímo úměrně s počtem prvků.
O něco pomalejší než lineární, ale stále velmi dobrá.
Doba běhu roste se čtvercem velikosti dat. Pokud se data zdvojnásobí, čas vzroste čtyřikrát.
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 |
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.
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“.