Asymptotická notácia

Čo je asymptotická (Big-O) notácia, príklady a interpretácia najčastejších výsledkov.

Typy asymptotických notácií

Asymptotická notácia sa v informatike používa pre vyjadrenie asymptotického správania algoritmu, teda ako sa jeho výkon mení pri veľkých hodnotách $n$.

Poznáme tri hlavné typy:

• Big-O: $O(n)$ – horná hranica, opisuje zložitosť algoritmu v najhoršom prípade;
• Big-Omega: $\mathrm{\Omega }(n)$ – dolná hranica, opisuje zložitosť algoritmu v najlepšom prípade;
• Theta: $\mathrm{\Theta }(n)$ – priemerný prípad;

V praxi sa snažíme, aby sa horná aj spodná hranica algoritmu čo najviac rovnala (snažíme sa o priemerný prípad). Ak sa rovnajú, znamená to že takáto výpočtová zložitosť algoritmu je ideálna.

Príklady pre určovanie asymptotických hraníc

Matematicky sa horná asymptotická hranica definuje ako:

$\begin{array}{rl}f(n)& =O(g(n))\\ \mathrm{\exists }c,m& >O\mathrm{\forall }n\ge m\\ f(n)& \le c\times g(n)\end{array}$

V preklade: O(n) je definovaná ako funkcia, pre ktorú existujú konštanty $c$ a $m$ ktoré sú väčšie ako O pre všetky $n\ge m$. Platí, že všetky hodnoty tejto funkcie sú menšie alebo rovné ako hodnoty pôvodnej funkcie $g(n)$ prenásobené konštantou $c$.

Dolná asymptotická hranica sa definuje podobne, iba hľadáme všetky hodnoty väčšie alebo rovné ako $c\times g(n)$:

$\begin{array}{rl}f(n)& =\mathrm{\Omega }(g(n))\\ \mathrm{\exists }c,m& >\mathrm{\Omega }\mathrm{\forall }n\ge m\\ f(n)& \ge c\times g(n)\end{array}$

V podstate pri týchto príkladoch iba hľadáme konštanty $c$ a $m$ pre daný typ hranice.

Majme napríklad:

$\frac{n+1}{2}=O(n)$

Máme zistiť, či výraz naľavo patrí asymptotickej hornej hranici. To znamená, že:

$\frac{n+1}{2}\le c\times n$

Za konštantu $c$ si môžme zvoliť akékoľvek kladné číslo. Predvolene je $c=1$:

$\begin{array}{rl}\frac{n+1}{2}& \le 1\times n\\ \frac{n+1}{2}& \le n\\ \end{array}$

Dostali sme rovnicu ktorú iba vypočítame. To, čo patrí výslednému $n$ bude naša konštanta $m$:

$\begin{array}{rl}\frac{n+1}{2}& \le n\\ n+1& \le 2n\\ 1& \le n\\ \\ & m=1;c=1\end{array}$

Skúsme to pre:

$\frac{n+1}{2}=\mathrm{\Omega }(n)$

Postup zostáva rovnaký, iba použijeme znamienko $\ge$ a konštantu $c=\frac{1}{2}$:

$\begin{array}{rl}\frac{n+1}{2}& \ge c\times n\\ \frac{n+1}{2}& \ge \frac{1}{2}n\\ n+1& \ge n\\ 1& \ge 0\to \text{platí pre všetky}n\\ & m=1;c=\frac{1}{2}\\ \end{array}$

Interpretácia výsledkov asymptotickej časovej zložitosti

Porovnanie časovej zložitosti pre rôzne asymptotické správania funkcií. Os Y ($N$) predstavuje 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

Pri Big-O 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$).

Ďalej, ak je za sebou viacero operácií s konštantným časom, neovplyvní to graf časovej zložitosti a tieto operácie môžu byť spolu chápané ako len jedna operácia s časom $O(1)$ ($O(1+5+n+1)=O(n)$ – oba grafy sú lineárne).

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)$.

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ť algoritmu

Podobne ako pri časovej, tak aj pri pamäťovej zložitosti môžeme využiť asymptotickú notáciu (Big-O). Má formu $O(g(n))$. Predstavuje, koľko dodatočnej pamäte spotrebuje algoritmus počas behu (dodatočnej preto, lebo neberieme ohľad na pamäť do ktorej sa uloží vstup alebo inštrukcie pre program). Pri pamäťovej zložitosti analyzujeme premenné, polia, pomocné štruktúry a 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) # jednoduchý print, nikde nič neukladáme

Ak to všetko dáme dokopy, získame $O(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é. Tu je jedno z riešení:

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 (s tým, že v pamäti bude spolu 20 prvkov, 10 na vstupe a 10 kde sme premenili všetky písmená na veľké - ale ako sme hovorili, zaujíma nás dodatočná pamäť a nie pamäť na vstupe, teda iba 10 prvkov s veľkými písmenami).

Detaily o výpočtovej zložitosti jednotlivých algoritmov sa budú nachádzať na ich stránkach ďalej v tejto téme.

Referencie

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

Asymptotické hranice výpočtovej zložitosti »