Izpitno vprašanje RAČ2PRA 2500

Iz MaFiRaWiki

GFDL Avtor tega članka je študent/ka Ivana.

Pripravil/a ga je pri predmetu Računalništvo 2 (FMF PRA).


Kljub temu ste vsi vabljeni k urejanju in popravkom, saj je bistvo wikija ravno v sodelovalnem delu.

Vprašanje

Razloži, kaj je to O notacija in kaj merimo z njo!

Odgovor

Notacijo uporabljamo za analizno algoritma.
Za veliko zanimivih algoritmov je štetje točnega števila operacij prezapleteno. Da poenostavimo analizo, določimo najhitreje rastoči faktor ter zanemarimo počasneje rastoče faktorje in konstantne faktorje. Tako dobljena formula je časovna zahtevnost algoritma. Poudarek je na hitrosti rasti časa, potrebnega za izvedbo.
Podobno naredimo za prostorsko zahtevnost.

Z O notacijo merimo prostorsko in časovno zahtevnost. Zahtevnost je seveda odvisna od števila podatkov, torej od obsežnosti problema v konkretnem primeru. Ko govorimo o časovni zahtevnosti, sta običajni enoti čas teka algoritma in število osnovnih aritmetičnih operacij (seštevanje, odštevanje, množenje, deljenje, primerjave, torej v računalniku vgrajene operacije). Označimo jo z O(X); pomeni da je notacija reda X.
X označuje red rasti, kjer zanemarimo počasneje rastoče člene in konstantne faktorje.


Po hitrosti urejenih nekaj primerov:

  • O(1) - konstantna zahtevnost - hitrost ni odvisna od vhodnih podatkov
  • O(log n) - logaritemska zahtevnost
  • O(n) - linearna zahtevnost
  • O(n log n) - zgled za subkvadratno zahtevnost (narašča hitreje kot linearna, počasneje od * kvadratne)
  • O(n2) - kvadratna zahevnost
  • O(nc) - polinomska zahtevnost - kjer je c konstanta
  • O(nlog n) - zgled za subeksponentno (vmesno) zahtevnost - (narašča hitreje kot katerikoli polinom in počasneje kot eksponentna.)
  • O(en) - eksponentna zahtevnost
Osebna orodja