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, nie sú tam žiadne cykly ani iné vetvenie).

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;

Teda, výsledok by teoreticky mohol byť

$O(6)$

. Tvárme sa, že číslo v zátvorke by predstavovalo počet operácií ktoré kód vykoná, avšak v praxi to funguje trochu inak. Poďme si to vysvetliť tak, že si to skomplikujeme a pridáme do rovnice premennú

$n$

:

# premenná "n" môže byť akékoľvek prirodzené číslo (väčšie ako alebo rovné nule)
# deklarácia by mohla vyzerať napríklad takto:
n = int(input())

def scitaj_prvych(n):
  """
  Funkcia, ktorá sčíta prvých `n` čísel a vráti výsledok sčítania.
  """
  sucet = 0 # konštantné priradenie, O(1)

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

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

V prvom rade vidíme problém: nemôžme pre všetky prípady jednoznačne určiť konštantný počet operácií, pretože veľkosť poľa (respektíve, počet čísiel ktoré sa sčítajú) sa mení v závislosti od vstupu, teda premennej

$n$

. Z toho vyplýva, že musíme odvodiť všeobecnú rovnicu ktorá bude hovoriť, ako sa časová náročnosť kódu bude meniť v závislosti od počtu prvkov na vstupe – aspoň približne. Mohlo by to vyzerať nejako takto:

n = int(input()) # tvárime sa, že O(1), ale tento riadok nebudeme brať do úvahy

# teoreticky aj vytvorenie a priradenie funkcie do pamäte je operácia,
# ale neberieme ju do úvahy
def scitaj_prvych(n):
  sucet = 0 # O(1), ale neberieme do úvahy

  # zaujíma nás iba táto časť
  for cislo in range(n): # n-krát
    sucet += cislo # O(1)

  return sucet # O(1), ale toto tiež neberieme do úvahy

Teda, ak berieme do úvahy iba cyklus, tak časová náročnosť je:

$O(1\times n)=O(n)$

.

🤔

Ale prečo sa vlastne tvárime, že polovica kódu neexistuje a neberieme ho do úvahy? Prečo nás zaujíma iba cyklus?

V predošlom príklade sme dospeli k záveru, že kód vykonal presne 6 operácií, a teda by sme to mohli teoreticky zapísať ako $O(6)$, pretože sme zistili že číslo v zátvorke predstavuje počet operácií ktoré kód vykoná.

Porovnanie výpočtovej zložitosti pre rôzne asymptotické správania funkcií - os Y ($N$) predstavuje (približný) počet operácií, os X ($n$) predstavuje počet prvkov na vstupe.

To ale nie je celkom pravda. Pravdou je, že pri Big-O (asymptotickej notácií) nás zaujíma iba hodnota ktorá má tendenciu rásť čo najrýchlejšie s meniacim sa vstupom. Inými slovami, notácia Big-O je len teoretická horná hranica – nehovorí o presnom počte operácií, ale o trende.

V poslednom príklade by sme pri aplikovaní predošlého postupu (teda, ak by sme brali do úvahy všetky alokácie konštánt a ostatné operácie) dostali ako výsledok niečo ako $O(1+\dots +n+\dots )$. No napokon sme nebrali súčty jednotiek do úvahy, a ako výsledok nám zostalo iba $O(n)$. Je to preto, že $n$ sa zo všetkých hodnôt mení najrýchlejšie v závislosti od vstupu.

Big-O sa používa na vyjadrenie asymptotického správania algoritmu, teda ako sa jeho výkon mení pri veľkých hodnotách $n$. Áno, mohli by sme brať do úvahy aj konštantné faktory $O(1)$, ale nemá to zmysel pretože pri veľkom množstve vstupných hodnôt sú zanedbateľné. Napokon, skúmame trend, to znamená že ak máme výsledok $O(1+n)$ a $O(1000000+n)$, oba naznačujú že trend je lineárny – konkrétny presný počet operácií nás teda nemusí zaujímať.

Ak by sme mali ako výsledok napríklad $O(n^2+n+1)$, zredukovali by sme ho iba na $O(n^2)$, pretože táto hodnota má tendenciu rásť najrýchlejšie podľa toho ako by sa menilo $n$ (rastie kvadraticky, a to má prednosť pred lineárnym alebo konštantným správaním). To, že to rastie kvadraticky nám stačí a neberieme do úvahy že to ešte rastie aj lineárne a že je tam aj konštantné správanie.