Asymptotická notácia

Čo je asymptotická (Big-O) notácia, časová vs. pamäťová zložitosť a interpretácia najčastejších výsledkov.

Asymptotická notácia

.

Časová zložitosť

Pri časovej zložitosti používame asymptotickú notáciu vo forme $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] # znovu O(1)
print(den) # 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. vytvorenie premennej den;
4. výpis tejto premennej na terminál;

Teda, výsledok by teoreticky mohol byť $O(4)$ (iba sčítame operácie: $O(1+1+1+1)$). Číslo v zátvorke by predstavovalo počet operácií ktoré kód vykoná - avšak, v praxi to nedáva zmysel, pretože cieľom nie je vypočítať presný počet operácií ktoré kód vykoná, ale iba určiť trend, podľa ktorého sa mení výkon algoritmu s meniacim sa objemom údajov na vstupe.

Aby sme ale mohli správne určiť pomer výkonu k vstupu, potrebujeme pridať premennú $n$, ktorá bude udávať počet prvkov na vstupe, napríklad:

# 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)

Vidíme, že počet čísiel ktoré sa majú sčítať sa dynamicky menia v závislosti od toho čo zadá používateľ do terminálu (respektíve, podľa toho aké číslo je v 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. Ak sa pozrieme na hlavný cyklus v kóde:

for cislo in range(n): # n-krát
  sucet += cislo # O(1)

Teda, výsledná rovnica je: $O(1\times n)=O(n)$ (počet operácií súčtu je rovný počtu čísel ktoré máme sčítať)

🤔

Čo sa vlastne myslí pod pojmom "operácia"? Aj najjednoduchšie inštrukcie môžu trvať niekoľko CPU cyklov - ako veľmi musíme kód deliť a "rozkúskovať"? A prečo nás vlastne zaujíma iba ten cyklus? Aj priradenie premennej n na začiatku je predsa operácia?

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$. Mohli by sme brať do úvahy aj konštantné faktory $O(1)$ (napríklad, priradenie premenných mimo hlavného cyklu programu), ale nemá to zmysel pretože pri veľkom množstve vstupných hodnôt sú alokácie pár (globálnych) premenných zanedbateľné a nezávisia priamo od premennej $n$. Skúmame iba trend, to znamená že ak máme napríklad dva výsledky: $O(1+n)$ a $O(1000000+n)$, oba naznačujú že trend je lineárny – presný počet operácií nás 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 pretože rastie najrýchlejšie v závislosti od $n$).

No a operácia je vlastne iba určitá abstrakcia nad nejakou časťou kódu ktorá niečo robí a má konštantný čas $O(1)$. Môže ísť napríklad o vykonanie nejakej funkcie, priradenie premennej, aritmetickú operáciu, ale aj napríklad porovnanie a výmenu prvkov v množine (v algoritme Bubble sort). Ak je za sebou viacero operácií s konštantným časom, neovplyvní to graf časovej zložitosti funkcie pretože konštantné operácie nezávisia priamo od $n$, a teda tieto operácie môžu byť spolu chápané ako len jedna operácia s časom $O(1)$.

Všeobecný postup pre výpočet časovej zložitosti

Všeobecný postup pre určenie časovej zložitosti by teda mohol vyzerať takto:

1. Identifikovať hlavnú slučku programu ktorá spracuje údaje zo vstupu, a teda jej výkon závisí od celkového množstva údajov na vstupe (zväčša od premennej $n$);
2. Zorientovať sa, čo táto časť kódu vlastne robí a koľko údajov je vlastne potrebné spracovať. Napríklad: je potrebné prejsť všetkými údajmi na vstupe, alebo môže nastať aj prípad že slučka skončí skôr? Spracujú sa všetky údaje alebo iba polovica? A podobne...;
3. Určiť časovú zložitosť operácií ktoré sú jednoznačné;
4. Dať to všetko dokopy (ak je to cyklus, pravdepodobne budeme násobiť toľkokrát, koľko sa kód bude opakovať, inak sčítavame)

Interpretácia výsledkov časovej zložitosti

Porovnanie časovej 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.

V tabuľke možno vidieť porovnanie najčastejších výsledkov asymptotickej notácie (pre časovú zložitosť):

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 }_{2}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\cdot {\log }_{2}n)$	Kvázilineá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

Konštantná časová zložitosť – $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...

Logaritmická časová zložitosť – $O({\log }_{2}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) postupne skracuje (neskráti sa naraz!) 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. Binárne vyhľadávanie hľadá prvok vo vopred zoradenom poli tak, že:

1. Skontroluje stredný prvok;
2. Ak je hľadaný prvok menší, pokračuje v ľavej polovici; ak je väčší, pokračuje v pravej polovici;
3. Opakuje sa to, kým nenájdeme prvok ktorý hľadáme alebo kým už nezostane žiadna podmnožina na hľadanie (v tom prípade sa tam prvok nenachádza);

Každým krokom zmenšíme veľkosť vyhľadávanej časti na polovicu.

🤔

Prečo je tam logaritmus a nie napríklad $O\left(\frac{n}{2}\right)$, ak sa vstup skráti o poloviu?

Pretože vstup sa skracuje postupne, neskráti sa celý naraz o polovicu. Ak začneme s poľom veľkosti $n$, postupne sa veľkosť vyhľadávanej časti zmenšuje:

Iterácia ($k$)	Počet zostávajúcich prvkov ($n$)	Poznámka
1. iterácia	$n$	Začiatočný počet všetkých prvkov ($n$).
2. iterácia	$\frac{n}{2}$	Prvý krát rozdelíme množinu na polovicu.
3. iterácia	$\frac{n}{2}÷2=\frac{n}{4}$	To, čo sme rozdelili ešte rozdelíme na polovicu.
4. iterácia	$\frac{n}{4}÷2=\frac{n}{8}$	Ešte delíme ďalej...
...	...	...až pokým nezostane nič, čo by sa dalo deliť (matematicky to avšak pokračuje donekonečna).

Vidíme, že číslo ktoré je v zlomku v menovateli (dole) je vždy výsledok $2^k$. Všeobecný vzorec pre výpočet zostávajúceho počtu prvkov v iterácií $k$ je teda: $\frac{n}{2^k}$.

Zastavíme sa keď zostane iba 1 prvok, teda keď $\frac{n}{2^k}=1$. Ak chceme určiť $k$, tak najprv vyjadríme $n$ ako $n=2^k$ a použijeme logaritmus aby sme dostali: $k={\log }_{2}n$. Časová zložitosť je teda vyjadrená ako: $O({\log }_{2}n)$.

ℹ️

Poznámka: $O({\log }_{2}n)$ je to isté ako $O(\log n)$.

O detailoch binárneho vyhľadávania a konkrétnej implementácií v Pythone si povieme neskôr v časti o binárnom vyhľadávaní.

Lineárna časová zložitosť – $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, napríklad koľko trvá prístup k prvku v poli (mení sa to v závislosti od výkonu hardvéru, aktuálneho zaťaženia počítača a tak ďalej...). Zaujíma nás všeobecný trend toho, ako sa výkon mení a to nám stačí pre jednoznačné určenie lepšieho algoritmu.

Kvázilineárna časová zložitosť – $O(n\cdot {\log }_{2}n)$

Kým v logaritmickej zložitosti ($O({\log }_{2}n)$) sa rozdeľuje v každom kroku celkový počet prvkov na polovicu, kvázilineárna zložitosť hovorí že každý prvok na vstupe je spracovávaný logaritmicky (teda, logaritmus $n$ sa násobí $n$-krát).

Táto zložitosť sa objavuje hlavne v efektívnych triediacich algoritmoch a v algoritmoch, ktoré kombinujú lineárnu a logaritmickú prácu (preto sa nazýva "kvázilineárna" – nie je úplne lineárna, ale ani úplne logaritmická). Medzi príklady patria: Merge sort, Quick sort, Heap sort.

Kvadratická časová zložitosť – $O(n^2)$

V praxi predstavuje kvadratická zložitosť najčastejšie algoritmy, ktoré využívajú pre prácu vnorené cykly (napríklad, triediaci algoritmus Bubble sort).

Exponenciálna časová zložitosť – $O(2^n)$

Horšia ako kvadratická zložitosť, exponenciálna zložitosť má ako exponent číslo $n$. Napríklad, povedzme že máme nájsť všetky kombinácie pre binárne číslo dĺžky $n$. Máme k dispozícií dva znaky (0 a 1), teda časová zložitosť pre algoritmus ktorý takéto kombinácie hľadá bude $O(2^n)$.

Ďalší prípad je, ak by sme mali napríklad nájsť a vyskúšať všetky kombinácie určitého hesla dĺžky $n$ (ak predpokladáme, že funkcia ktorá heslo vyskúša má konštantnú časovú zložitosť $O(1)$ a heslo sa skladá iba z čísiel od 0 po 9). Časová zložitosť by bola $O(10^n)$, teda vieme zistiť presný počet operácií pre dĺžku hesla $n$. Avšak, pre stanovenie typu časovej zložitosti sa ako základ väčšinou konvenčne uvádza iba číslo 2 (teda, $O(2^n)$), pretože nám to stačí pre vyjadrenie že čas rastie exponenciálne.

Faktoriálová časová zložitosť – $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. Takže, vo všeobecnosti sa vždy snažíme zložitosti $O(n!)$ vyhnúť.

Č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.

Pamäťová zložitosť

Podobne ako pri časovej, tak aj pri pamäťovej zložitosti využívame asymptotickú notáciu (Big-O). Predstavuje, koľko dodatočnej pamäte spotrebuje algoritmus počas behu (dodatočnej preto, že neberieme ohľad na pamäť do ktorej sa uložia prvky na vstupe). Pri pamäťovej zložitosti analyzujeme premenné, polia, pomocné štruktúry, rekurzívne zásobníky.

Niektoré algoritmy šetria pamäť, ale sú pomalšie. Naopak, iné sú rýchlejšie ale zaberajú viacej pamäte. Preto neexistuje jeden najlepší algoritmus, a treba si vybrať (aj po zvážení časovej zložitosti) aký algoritmus použijeme. Ak spracovávame malé množstvo dát, pravdepodobne budeme priorizovať lepšiu časovú zložitosť. Pri veľkom množstve dát budeme brať ohľad aj na zväčšujúcu sa pamäťovú náročnosť.

Tu je náš predošlý kód:

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"

Je možné vypočítať, koľko zaberie celý takýto program miesta v pamäti, presne na bajty. Avšak, podobne ako pri časovej zložitosti kde neriešime presný počet operácií, aj pri pamäťovej zložitosti nás bude zaujímať iba trend (graf toho, ako náročnosť klesá alebo sa zvyšuje v závislosti od objemu dát na vstupe, teda

$n$

). Kód vyššie by sa dal analyzovať takto:

DNI = ["Pondelok", "Utorok", "Streda", "Štvrtok", "Piatok", "Sobota", "Nedeľa"]
# toto predstavuje akoby premennú "n"
# môžme ju ignorovať, pretože pamäťová zložitosť vstupných dát nás nezaujíma,
# zaujíma nás iba dodatočná pamäť ktorú program potrebuje počas behu

poradie_v_tyzdni = 3          # je to jednoduché priradenie konštanty...
den = DNI[poradie_v_tyzdni-1] # ...rovnako aj tu
# preto je zložitosť pre obidva riadky vyššie = O(1)

print(den) # môžme iba predpokladať pamäťovú zložitosť O(1)

Ak to všetko dáme dokopy, získame

$O(1+1+1)$

. Po zanedbaní nižších rádov má kód vyššie pamäťovú zložitosť

$O(1)$

. Čo ak by sme mali iný kód. Napríklad, chceme všetky reťazce na vstupe transformovať na reťazce, kde budú všetky písmená veľké. Kód by vyzeral nasledovne:

def na_velke(n):
  vsetky_velke = []

  for retazec in n:
    novy = retazec.upper()    # konverzia na reťazec kde sú všetky písmená veľké
    vsetky_velke.append(novy) # pridáme nový reťazec do výslednej množiny

  return vsetky_velke

Časová zložitosť je samozrejme

$O(n)$

- čím väčší máme zoznam na vstupe, tým viac operácií (iterácií) bude kód vykonávať, teda časová zložitosť rastie lineárne. Rovnako je to aj s pamäťovou zložitosťou, ktorá je tiež

$O(n)$

- dodatočná pamäť, ktorú program spotrebuje rastie lineárne s pamäťou kde sú uložené vstupné prvky. Inými slovami, ak máme na začiatku 10 prvkov, tak naspäť aj 10 prvkov dostaneme.

Referencie

« Úvod do výpočtovej zložitosti

Určovanie počtu operácií v rekurzívnych volaniach »