Časová zložitosť

Keď máme dva algoritmy na riešenie rovnakého problému, ako zistíme, ktorý je lepší? Nestačí len odmerať čas na konkrétnom počítači — výsledok by závisel od rýchlosti počítača. Namiesto toho používame časovú zložitosť.

Čo je časová zložitosť?

Časová zložitosť popisuje, ako rastie počet operácií algoritmu keď sa zväčšuje veľkosť vstupu (zvyčajne označovaná N). Zaujíma nás trend rastu, nie presný počet.

Big O notácia

Big O (píše sa O()) vyjadruje horný odhad rastu — najhorší možný prípad. Ignoruje konštanty a menej dôležité členy.

Príklady:

• O(1) — konštantná — nezávisí od N
• O(log N) — logaritmická — veľmi pomalý rast
• O(N) — lineárna — priamo úmerná N
• O(N log N) — kvázilineárna — trochu horšia ako lineárna
• O(N²) — kvadratická — rast N² pri zdvojnásobení N
• O(2ᴺ) — exponenciálna — veľmi rýchly rast

Vizuálne porovnanie

Pre N = 10, 100, 1000:

O(1) — Konštantná zložitosť

Algoritmus trvá rovnako dlho bez ohľadu na veľkosť vstupu:

def prvý_prvok(zoznam):
    return zoznam[0]   # vždy jeden krok, bez ohľadu na dĺžku

def je_parné(n):
    return n % 2 == 0  # jeden výpočet

O(N) — Lineárna zložitosť

Čas rastie priamo úmerne s N:

def najdi_maximum(zoznam):
    maximum = zoznam[0]
    for prvok in zoznam:     # N iterácií
        if prvok > maximum:
            maximum = prvok
    return maximum

Pre N=100 → ~100 operácií. Pre N=1000 → ~1000 operácií.

O(N²) — Kvadratická zložitosť

Typická pre vnorené cykly, kde každý závisí od N:

def bublinkove_triedenie(zoznam):
    n = len(zoznam)
    for i in range(n):          # N iterácií
        for j in range(n - 1):  # N iterácií
            ...   # N × N = N² operácií

O(log N) — Logaritmická zložitosť

Typická pre "rozdeľuj a panuj" algoritmy — napr. binárne vyhľadávanie:

def binarne_vyhladavanie(zoznam, ciel):
    lava, prava = 0, len(zoznam) - 1
    while lava <= prava:
        stred = (lava + prava) // 2
        if zoznam[stred] == ciel:
            return stred
        elif zoznam[stred] < ciel:
            lava = stred + 1    # eliminuje polovicu
        else:
            prava = stred - 1   # eliminuje polovicu
    return -1

V každom kroku sa priestor hľadania halvuje → log₂(N) krokov celkovo.

Pravidlá Big O

1. Ignoruj konštanty: O(2N) = O(N), O(100) = O(1)
2. Berie sa dominantný člen: O(N² + N) = O(N²)
3. Najhorší prípad: O udáva horný limit

# Toto má zložitosť O(N), nie O(2N):
def dvojpruchod(zoznam):
    for x in zoznam: print(x)   # N operácií
    for x in zoznam: print(x)   # N operácií
    # Celkovo 2N, ale O(N) — konštanta 2 sa ignoruje

Zložitosť bežných operácií v Pythone