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?

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

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í;
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;
Použiť asymptotickú analýzu
- Zanedbať konštanty a nižšie rády (napr. $O (2 n)$ 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í:

vytvorenie premennej DNI;
vytvorenie premennej poradie_v_tyzdni;
výpočet správneho indexu;
zobratie prvku z poľa;
vloženie hodnoty do premennej den;
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.

Príklady výpočtov