Veľké O

Keďže čas meriame počítaním elementárnych operácií, a každá z týchto operácií môže v skutočnosti trvať iný čas, nemá zmysel porovnávať absolútne počty. Namiesto toho potrebujeme spôsob, ako porovnávať algoritmy, kde na konštatnách nezáleží.

Na to slúži takzvaná O-notácia, alebo asymptotické určovanie zložitosti, často nazývané aj Veľké O. Pomáha nám pochopiť, ako sa správa program, keď sa veľkosť vstupu zväčšuje. Nezaujímajú nás malé vstupy, ale tie, ktoré si vyžadujú milióny operácií. A navyše nechceme byť zbytočne presní – rozdiel medzi 1000000 a 1000042 operáciami je zanedbateľný.

Intuitívne pochopenie Veľkého O

Počet elementárnych operácií, ktoré program vykoná, sa dá vyjadriť ako funkcia od veľkosti vstupu. Ak máme na vstupe číslo $n$, bude to funkcia tohto čísla. Chceme porovnávať, ako rýchlo tieto funkcie rastú. Čím rýchlejšie funkcia rastie, tým viac operácií bude treba.

Pozrime sa na príklad. Majme program, ktorý vykoná $f(n)=n^2/2+5n+4$ operácií. Ako zistíme jeho zložitosť pomocou Veľkého O?

1. Zanedbáme konštanty: Či urobíme $n$ alebo $5n$ operácií, je z hľadiska rastu funkcie skoro jedno. Konštanta 5 nezávisí od veľkosti vstupu, preto by sme si napríklad mohli kúpiť 5-krát rýchlejší počítač, a rozdiel medzi algoritmami by sme zakryli. Rovnako zanedbáme konštantné členy ako 4 a koeficienty ako 1/2. Takže z $f(n)=n^2/2+5n+4$ sa stane len niečo ako $f(n) = n^2+n$.
2. Zaujíma nás len najväčší člen: Spomedzi členov $n^2$ a $n$ rastie $n^2$ oveľa rýchlejšie ako $n$. Pre veľké $n$ bude hodnota $n^2$ dominovať nad $n$. Preto si vyberieme ten člen, ktorý rastie najrýchlejšie. V tomto prípade je to $n^2$.

Intuitívne je poradie zložitostí: $1 <= log^a(n) <= n^a <= a^n <= n! <= n^n$.

Výsledkom je odhad, že náš program vykoná rádovo $n^2$ operácií. Toto sa zapisuje ako $O(n^2)$. Keď povieme, že časová zložitosť programu je $O(n^2)$, znamená to, že program vykoná najviac rádovo $n^2$ krokov.

Možno sa to zdá príliš zjednodušené, ale pre porovnávanie algoritmov je to úplne postačujúce.

Pri odhade časovej zložitosti sa nám často môže zísť Theoretical Computer Science Cheatsheet.