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, môžeme tvrdiť že 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)$. Číslo v zátvorke by predstavovalo počet operácií ktoré kód vykoná - avšak, v praxi to funguje trochu inak. Nemá zmysel analyzovať konštantný vstup, pretože chceme vidieť ako sa výkon algoritmu mení s rôznym množstvom prvkov (údajov) na vstupe, a to zabezpečíme iba pomocou premennej $n$.

Poďme si to teda 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, neskôr zistíme prečo

# 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é hodnoty, teda všetky čísla 1, sa nikdy nemenia. To čo sa mení najviac je samotné $n$.

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ú alokácie pár (globálnych) premenných pred hlavnou slučkou programu (to jest, v našom prípade pred cyklom for) zanedbateľné. Napokon, skúmame iba trend, to znamená že ak máme dva výsledky: $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.

No, možno by bolo dobré urobiť si prehľad najčastejších výsledkov (pozri graf vyššie) a vysvetliť si ich:

Big-O notácia	Typická rýchlosť	Príklad algoritmu
$O(1)$	Konštantná	Prístup k prvku v množine pomocou indexu alebo k hodnote v slovníku pomocou kľúča.
$O(\log n)$	Logaritmická	Binárne vyhľadávanie (ak sú všetky prvky vopred správne zoradené)
$O(n)$	Lineárna	Prechod cez všetky prvky v množine
$O(n\log n)$	Quasilineárna	Efektívne triedenie (merge-sort, quick-sort)
$O(n^2)$	Kvadratická	Vnorené cykly (bubble-sort)
$O(2^n)$	Exponenciálna	Rekurzívny výpočet Fibonacciho postupnosti
$O(n!)$	Faktoriálová	Brute-force permutácie

$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(\log n)$

Aha, máme tu aj obľúbené logaritmy! Samozrejme je za tým matematika ktorá funguje, ale pre uľahčenie života si stačí iba zapamätať:

Ak sa veľkosť spracovávaného vstupu (prvkov) skráti o polovicu, tak tento algoritmus bude mať logaritmickú rýchlosť.

Obľúbeným príkladom z praxe je napríklad binárne vyhľadávanie. Ak nevieš ako fungujú binárne stromy, tu je jeden príklad. Vľavo sú prvky ktoré sú menšie ako aktuálny rodič a vpravo sú väčšie prvky ako aktuálny rodič:

Vždy je garantované, že (pri správnom aplikovaní algoritmu) vyhľadávanie nejakého prvku zaberie o polovicu menej krokov ako keby sme prehľadávali celú množinu, prvok po prvku.

Napríklad, povedzme že chceme nájsť číslo 13. Začíname od čísla 4 úplne hore. A zakaždým sa pýtame: je hľadané číslo (13) menšie alebo väčšie ako aktuálne číslo (4)? Ak je väčšie = doprava, ak je menšie = doľava. Teda, 13 je väčšie, ideme doprava na číslo 5. 13 je stále väčšie ako 5, ideme doprava na 18. 13 je menšie ako 18, ideme doľava. A práve tam končíme, pretože sme našli prvok 13 ktorí sme hľadali.

Dáva to zmysel - nech je množina akákoľvek dlhá s akýmikoľvek číslami, pri vyhľadávaní budeme mať vždy iba 2 možnosti, pričom vždy môžme ísť iba po jednej vetve. Teda, počet vstupu ktorý musíme spracovať sa skrátil o polovicu - o polovicu sa skráti aj množstvo krokov v algoritme ktoré musíme aplikovať, a teda sa matematicky musí skrátiť aj celkový čas hľadania (o polovicu), čo je vyjadrené ako $O(\log n)$.

$O(n)$

Pravdepodobne asi najčastejší prípad v praxi. Predstavuje lineárnu rýchlosť algoritmu - inými slovami, o koľko viac prvkov pridáme do vstupu, o toľko sa spomalí algoritmus. Ak by sme mali balík kariet, znamenalo by to napríklad že chceme zrátať koľko tam tých kariet je. No a aby sme to spravili, musíme prejsť každou kartou v balíku. Ak máme 10 kariet, zrátame ich relatívne rýchlo, no pri milióne by sme už mali problém.

ℹ️

Poznámka: Pri výpočtovej zložitosti vždy predpokladáme že každá operácia - v našom prípade prirátanie každej karty do celkového počtu - nám zaberie rovnaký čas, napríklad pol sekundy. To znamená, že 10 kariet by sme rátali 5 sekúnd, milión kariet by sme v tom prípade rátali približne 140 hodín).
Ale ako sme hovorili predtým, zaujíma nás iba trend - pretože aj tak nedokážeme rozpočítať koľko trvajú jednotlivé procesy v počítači (mení sa to v závislosti od výkonu hardvéru, aktuálneho zaťaženia počítača a tak ďalej...).

$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=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 množstve kariet trvať niekoľko minút, no pri väčších číslach sa môžeme 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...