Asymptotická notácia

Čo je asymptotická notácia, všeobecný postup pre výpočet Big-O notácie, príklady výpočtov

Asymptotická notácia?

Asymptotická notácia

$O(f(n))$

predstavuje, koľko operácií vykoná určitý kód pre

$n$

prvkov na vstupe. Inými slovami, majme napríklad tento kód pre zistenie názvu dňa podľa jeho poradia v týždni (1 až 7):

DNI = ["Pondelok", "Utorok", "Streda", "Štvrtok", "Piatok", "Sobota", "Nedeľa"]
#           0         1          2         3         4         5          6

poradie_v_tyzdni = 3          # tretí deň v týždni
den = DNI[poradie_v_tyzdni-1] # -1, pretože indexujeme od 0

print(den)
# "Streda"

Tento kód je jednoduchý, ale aká je jeho časová náročnosť?

Všeobecný postup výpočtu

1. Identifikovať základné operácie
   • Zistiť, aké operácie sa v algoritme vykonávajú a koľko ich je;
   • Zamerať sa hlavne na slučky (for, while), rekurziu a volanie funkcií;
2. Vyjadriť počet vykonaných operácií ako funkciu vstupu $n$
   • Počet iterácií v cykle priamo určuje počet vykonaných operácií;
   • Podmienky a ostatné vetvy sa analyzujú oddelene;
3. Použiť asymptotickú analýzu
   • Zanedbať konštanty a nižšie rády (napr. $O(2n)$ sa zjednoduší na $O(n)$).
   • Zamerať sa na najdominantnejší člen (napríklad, $O(n^2+n)$ sa zjednoduší na $O(n^2)$).

Operácie, ktoré kód vyššie vykonáva, môžeme rozpísať a analyzovať. Interpretácia mojej analýzy je zobrazená nižšie:

DNI = ["Pondelok", "Utorok", "Streda", "Štvrtok", "Piatok", "Sobota", "Nedeľa"]
# alokuje sa premenná "DNI" a priradí sa jej hodnota
# z hľadiska časovej náročnosti sú konštanty O(1)
# (pretože prebehne práve 1 operácia, teda vytvorenie premennej)

poradie_v_tyzdni = 3
# toto je stále konštanta, takže O(1)

den = DNI[poradie_v_tyzdni-1]
# na prvý pohľad sa môže zdať, že v tomto riadku je opäť
# iba jedna operácia - vytvorenie premennej
# no netreba však zabudnúť, že kód by sa mohol rozdeliť aj takto:
#  poradie_minus_1 = poradie_v_tyzdni - 1 # 1. operácia - výpočet správneho indexu, O(1)
#  prvok_v_poli = DNI[poradie_minus_1]    # 2. operácia - výber prvku z poľa, O(1)
#  den = prvok_v_poli                     # 3. operácia - priradenie vybraného prvku do premennej, O(1)
# ...a toto sú až 3 operácie, z toho každá má náročnosť O(1)

print(den)
# ak by sme zobrazili zdrojový kód funkcie "print",
# zistili by sme že tiež vykonáva nejaké operácie
# a každá z nich môže mať inú časovú komplexitu
# ("print" musí predsa obsahovať ďalšie funkcie,
# ktoré sa starajú o výpis jednotlivých znakov do terminálu)
#
# ...avšak, ak by sme mali analyzovať aj tieto vstavané funkcie, boli by
# sme tu do rána - a vôbec, ak analyzujeme efektivitu kódu, pravdepodobne nás bude
# zaujímať náš vlastný kód, nie efektivita funkcie "print"
# zjednodušene povedané, budeme predstierať že aj toto je O(1)

Tuto sa ešte nenachádza žiadna premenná

$n$

(keďže vstup sa pre kód nikdy nemení, vždy máme pevne danú množinu 7. dní a vyberáme práve jeden - žiadne cykly ani vetvy).

Nezáleží na tom, koľkokrát kód vyššie spustíme, vždy sa vykoná práve 6 operácií:

1. vytvorenie premennej DNI;
2. vytvorenie premennej poradie_v_tyzdni;
3. výpočet správneho indexu;
4. zobratie prvku z poľa;
5. vloženie hodnoty do premennej den;
6. výpis tejto premennej na terminál;

Avšak, výsledok sa nezapisuje ako $O(6)$, ale iba $O(1)$. Je to z toho dôvodu, že zápis $O(1)$ hovorí, že pre akýkoľvek počet prvkov $n$ na vstupe je časová náročnosť kódu konštantná. V podstate, teoreticky aj $O(6)$ hovorí, že časová náročnosť je konštantná, ale pre správnosť treba uvádzať $O(1)$ - treba si iba uvedomiť, že číslo v zátvorkách nevyjadruje presný počet operácií ktoré kód vykoná, ale je to iba vyjadrenie ako by mohol vyzerať graf časovej náročnosti funkcie z hľadiska meniaceho sa vstupu.

Uh, to začína byť komplikované - grafy? A čo je vlastne to veľké

$O$

? No, poďme sa vrátiť späť a vysvetliť to na prvom reálnom príklade. Majme kód:

# premenná "n" môže byť akékoľvek prirodzené číslo (väčšie ako alebo rovné nule)
# v kóde deklaráciu tejto premennej už ďalej nebudem uvádzať, a ani sa táto deklarácia
# neráta ako operácia ktorú kód vykonáva - nás zaujíma iba to, čo sa deje "vnútri"
# nejakej funkcie, a nie všetky nepodstatné detaily okolo nej
n = ...

# ak nevieš čo to robí - vytvorí množinu číselných hodnôt ("int")
# načítaných zo vstupu na terminály, oddelených čiarkou
# časová náročnosť je O(1), pretože nepoznáme (resp. nechceme poznať :))
# zdrojový kód týchto funkcií, teda to ako sú implementované v Pythone
# ...ale, nás aj tak iba zaujíma telo funkcie
pole = list(map(int, input().split())

def scitaj_pole(n):
  sucet = 0 # konštantné priradenie, O(1)

  # toto si vysvetlíme nižšie
  # (spoiler: bude nás zaujímať iba toto :))
  for prvok in pole:
    sucet += prvok

  return sucet # = 15
  # aj operácia vrátenia ("return") sa pokladá za náročnosť O(1)

.