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"

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 v ktorej je 7 prvkov (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 (dáva to zmysel, pretože konštantné jednotky sa nikdy nemenia, teda to čo sa mení najviac je samotné $n$, duh...).

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. To je ozajstný zmysel toho, čo sa nazýva asymptotická notácia, teda Big-O.

Pre lepšie pochopenie si pozrime graf vyššie a vysvetlime si najčastejšie výsledky:

$O(1)$

Najlepší prípad je konštantný faktor, teda $O(1)$. V analógií z reálneho života by to napríklad znamenalo, že máme balíček kariet a chceme vybrať prvú kartu – a to urobíme okamžite, bez ohľadu na to koľko kariet je v balíčku. Môže ich tam byť 32, ale mohlo by ich byť aj 1 000, no prvú kartu vyberieme vo všetkých prípadoch vždy prakticky okamžite, teda je to iba akoby sme vykonali len jednu operáciu.

Konkrétne príklady z programovania sú napríklad jednoduché aritmetické operácie (sčítanie, odčítanie, násobenie, delenie...), výber konkrétneho prvku na n-tej pozícií v indexovanom poli, vrátenie hodnoty a podobne...

$O(n!)$

Najhorší prípad je $O(n!)$. Ak si zabudol, ten "výkričník" v matematike sa nazýva faktoriál a je to súčin všetkých prvkov od $n$ po 1 – napríklad, $5!$ znamená: $5\times 4\times 3\times 2\times =120$.

$O(n!)$ znamená že máme napríklad balík kariet na ktorých sú čísla. Tieto karty chceme zoradiť od najväčšieho čísla po najmenšie. Ale robíme to takým spôsobom, že karty vyhodíme do vzduchu a dúfame že padnú na zem správne zoradené. Predpokladáme teda, že musíme vykonať všetky možné kombinácie operácií pre to, aby sme ich niekedy vytriedili správne (preto je tam ten faktoriál, kombinatorika funguje...). To môže pri malom počte kariet trvať niekoľko minút, no pri väčších číslach sa môžme trápiť bezvýsledne aj niekoľko rokov...

Čo je aj dôvod, prečo vlastne všetko toto počítame a analyzujeme. Je rozdiel, ak nejaký algoritmus trvá pár sekúnd versus pár rokov, že? Naším cieľom je samozrejme tvoriť algoritmy ktoré sú efektívne a prehľadné. A Big-O notácia nám umožňuje porovnávať výkon dvoch rozličných algoritmov matematicky pre veľké vstupy. A keďže sme v dobe kedy bežne pracujeme s veľkým objemom dát na dennej báze, je veľmi dôležité aby bolo všetko čo najrýchlejšie – pretože nikto nemá čas a každý sa vždy všade iba ponáhľa...