Asymptotické hranice výpočtovej zložitosti

Asymptotická horná a dolná hranica funkcie zložitosti, najlepší, priemerný a najhorší prípad, asymptotická presná notácia.

Algoritmy, s ktorými sme sa streli v predošlej téme mali rôzne hranice ich výpočtových zložitostí. Ale čo to vlastne znamená že tieto funkcie majú určitú hranicu?

Vysvetlime to na jednoduchom kóde:

# existuje n.index(...), ale to by sme si toho moc neukázali:
def najdi_index_prvku(zoznam, hladaj):
  for n, prvok in enumerate(zoznam): # n = index aktuálneho prvku
    if prvok == hladaj:
      return n

  return -1 # prvok sa nenašiel

Časová zložitosť tohto algoritmu je $O(n)$ (lineárna), priestorová $O(1)$ (konštantná – nepoužíva dodatočnú pamäť).

Keďže zoznam na vstupe je usporiadanou množinou, môže nastať viacero situácií. Napríklad:

zoznam = [1, 2, 3]

hladaj = 4
index = najdi_index_prvku(zoznam, hladaj)
print(index) # vypíše -1
# prvok neexistuje, musíme teda prejsť celým zoznamom
# časová zložitosť je preto O(n)
# (ak predpokladáme, že prvok sa nikdy nebude v zozname nachádzať = najhorší prípad)

hladaj = 1
index = najdi_index_prvku(zoznam, hladaj)
print(index) # vypíše 0
# číslo 1 sa nachádza na prvom indexe (0), čo predstavuje najlepší (ideálny) prípad
# ak by sa hľadaný prvok vždy nachádzal na prvom mieste
# (teda, vždy by sme mali ideálne podmienky a najlepší prípad), tak by zložitosť bola
# konštantná = O(1), pretože by sme vykonali iba jednu operáciu porovnania

Vidíme dva prípady:

• V prvom je časová zložitosť $O(n)$, pretože musíme prejsť všetkými prvkami v zozname – a nakoniec zistíme, že sa tam prvok aj tak nenachádza.
  • Toto sa nazýva: najhorší prípad;
  • Vyjadruje ju notácia Big-O: $O(f(n))$;
• V druhom prípade je časová zložitosť $O(1)$, pretože hľadaný prvok sa nachádza na prvom mieste, vykonáme teda iba jednu operáciu porovnania (a zložitosť je konštantná).
  • Toto sa nazýva: najlepší prípad;
  • Vyjadruje ju notácia Omega: $\mathrm{\Omega }(f(n))$;
• Poznámka: v oboch prípadoch je priestorová zložitosť $O(1)$, pretože samotný algoritmus nepotrebuje žiadnu dodatočnú pamäť ktorá by sa menila v závislosti od $n$.

Z toho vyplýva, že v závislosti od usporiadania prvkov na vstupe a hodnoty ktorú hľadáme sa môže zmeniť aj výpočtová zložitosť algoritmu. Avšak, v praxi sme pesimisti a najčastejšie vždy vyjadrujeme Big-O notáciu (teda, $O(f(n))$), pretože predpokladáme Murphyho zákon, teda:

Všetko čo sa môže pokaziť, sa pokazí.

Asi si vieš predstaviť, že to tak naozaj funguje. Ale niekedy je možno užitočné vyjadriť aj priemerný prípad – je to v podstate spojenie hornej a dolnej hranice funkcie výpočtovej zložitosti, a vyjadrujeme ju ako Theta: $\mathrm{\Theta }(f(n))$. Theta notáciu môžeme použiť iba vtedy, ak vieme že priemerná zložitosť je presne ohraničená zhora aj zdola rovnakou funkciou.

V skratke:

• Ak vieme len hornú hranicu, ale nie dolnú, použijeme Big-O notáciu;
• Ak vieme len dolnú hranicu, ale nie hornú, použijeme Omega notáciu;
• Ak je rast výpočtovej zložitosti algoritmu presne obmedzený rovnakou funkciou zhora aj zdola, použijeme Theta notáciu;

Najhorší prípad

.

Najlepší prípad

.

Priemerný prípad

Existuje aj algoritmus, ktorý dokáže obsiahnuť všetky príklady:

def spocitaj_prvky(mnozina):
  pocet = 0

  for _ in mnozina:
    pocet += 1

  return pocet

V tomto algoritme je najhorší prípad zároveň aj najlepším. Bez ohľadu na veľkosť alebo usporiadanie prvkov v poli musíme vždy prejsť všetkými prvkami. Preto sú všetky notácie časovej zložitosti lineárne:

• pre hornú (Big-O) hranicu: $O(n)$;
• pre dolnú (Omega) hranicu: $\mathrm{\Omega }(n)$;
• pre priemernú (Theta) hranicu: spojenie hornej a dolnej hranice, v podstate stále iba $\mathrm{\Theta }(n)$;

Ale formálne môžme uviesť iba priemerný prípad (Theta notáciu), teda $\mathrm{\Theta }(n)$.

« Asymptotická notácia

Triediace algoritmy a ich výpočtová zložitosť »