Co je to notace velké O?

Notace Big O (Big O) je matematická notace používaná na popis asimptotického správania funkcie a jej horného limitu. V kontexte vývoja softvéru sa používa na hodnotenie výkonu algoritmov z hľadiska spotreby času (časová zložitosť) a pamäti (priestorová zložitosť) s rastúcim veľkosťou vstupných dát. Popisuje najhorší scenár vykonávania.

Najbežnejšie triedy časovej zložitosti:

• O(1): Konštantný čas. Čas vykonávania nezávisí od veľkosti vstupných dát.
• O(log n): Logaritmický čas. Čas vykonávania rastie pomaly s rastom veľkosti vstupných dát (napríklad binárne vyhľadávanie).
• O(n): Lineárny čas. Čas vykonávania je úmerný veľkosti vstupných dát (napríklad lineárne vyhľadávanie).
• O(n log n): Lineárno-logaritmický čas. Často sa vyskytuje v efektívnych algoritmoch triedenia (napríklad rýchle triedenie, merge sort).
• O(n^2): Kvadratický čas. Čas vykonávania rastie úmerne štvorcu veľkosti vstupných dát (napríklad bublinkové triedenie, výberové triedenie).
• O(2^n): Exponenciálny čas. Čas vykonávania rastie veľmi rýchlo s rastom veľkosti vstupných dát. Často v úplnom prehľadávaní.

Príklady kódu a ich časová zložitosť:

// O(1)
int prvýPrvok = pole[0];

// O(n)
for (int i = 0; i < pole.length; i++) {
    // nejaká operácia
}

// O(n^2)
for (int i = 0; i < pole.length; i++) {
    for (int j = 0; j < pole.length; j++) {
        // nejaká operácia
    }
}

Notácia Big O sa zameriava na dominantný člen v výraze a ignoruje konštanty a menej významné členy, pretože pri veľkých vstupoch ich príspevok je zanedbateľný. Napríklad algoritmus s komplexnosťou O(2n^2 + 5n + 10) sa považuje za O(n^2).

Pochopenie Big O je dôležité pre výber najefektívnejších algoritmov a dátových štruktúr pri vývoji.