Keď programujeme, nestačí napísať kód, ktorý funguje. Musíme sa tiež pýtať: Ako rýchlo funguje? Zložitosť algoritmu nám pomáha odpovedať na túto otázku — aj bez spustenia programu.
Čo je Big-O notácia
Big-O notácia (veľké O) popisuje, ako sa čas behu (alebo pamäťová náročnosť) algoritmu mení v závislosti od veľkosti vstupu n. Zaujíma nás správanie pre veľké hodnoty n — hovoríme o asymptotickej zložitosti.
Zjednodušene: Big-O popisuje najhorší prípad — koľko krokov algoritmus vykoná maximálne.
Big-O zanedbáva konštanty a menej dominantné členy. Napríklad 3n + 5 sa zapíše ako O(n), pretože pre veľké n dominuje lineárna závislosť.
Najdôležitejšie triedy zložitosti
O(1) — konštantná zložitosť
Algoritmus vždy vykoná rovnaký počet krokov bez ohľadu na veľkosť vstupu. Prístup k prvku poľa podľa indexu je O(1).
def prvy_prvok(zoznam):
return zoznam[0] # vždy jeden krok, bez ohľadu na veľkosť zoznamu
O(n) — lineárna zložitosť
Počet krokov rastie lineárne s veľkosťou vstupu. Lineárne vyhľadávanie je O(n).
def najdi_maximum(zoznam):
maximum = zoznam[0]
for prvok in zoznam: # n krokov
if prvok > maximum:
maximum = prvok
return maximum
O(n²) — kvadratická zložitosť
Počet krokov rastie so štvorcom veľkosti vstupu. Bubble sort je O(n²). Pre 10 prvkov to je ~100 krokov; pre 1000 prvkov ~1 000 000 krokov.
def bubble_sort(zoznam):
n = len(zoznam)
for i in range(n): # vonkajší cyklus: n krát
for j in range(n - 1): # vnútorný cyklus: n krát
if zoznam[j] > zoznam[j + 1]:
zoznam[j], zoznam[j + 1] = zoznam[j + 1], zoznam[j]
Porovnanie tried zložitosti
| Notácia | Názov | n = 10 | n = 1000 |
|---|---|---|---|
O(1) | Konštantná | 1 | 1 |
O(log n) | Logaritmická | ~3 | ~10 |
O(n) | Lineárna | 10 | 1 000 |
O(n log n) | Linearitmická | ~33 | ~10 000 |
O(n²) | Kvadratická | 100 | 1 000 000 |
Algoritmy s kvadratickou alebo horšou zložitosťou sa pre veľké vstupy stanú nepoužiteľne pomalými. Vždy hľadajte efektívnejšie riešenie, keď pracujete s veľkými dátami.
Časová vs pamäťová zložitosť
Rozlišujeme dve hlavné dimenzie zložitosti:
- Časová zložitosť — počet operácií (krokov), ktoré algoritmus vykoná.
- Pamäťová zložitosť — množstvo pamäte (premenné, štruktúry), ktoré algoritmus potrebuje.
Niekedy si môžeme vybrať: buď algoritmus pobeží rýchlejšie (menej krokov), ale spotrebuje viac pamäte, alebo bude pomalší, ale pamäťovo úspornejší. Tomuto kompromisu hovoríme time-space tradeoff.
Cvičné príklady
Algoritmus má dva vnorené cykly, každý prechádza n prvkov. Aká je jeho časová zložitosť?