Notacija O

Iz MaFiRaWiki

Ta članek ali del članka je v delu. Veseli bomo, če ga boste dopolnili in popravili.

Kaj pomeni to opozorilo?

Notacija "veliki O" je zapis množice funkcij, ki so asimptotično do konstantnega faktorja manjše od dane funkcije. Natančneje, za f : \mathbb{N} \to \mathbb{R} je

O(f) = \{g : \mathbb{N} \to \mathbb{R} \mid (\exists n_0, c)(\forall n \geq n_0)\; g(n) \leq c \cdot f(n)\}.

Kadar je g \in O(f) to preberemo "g je od nekod naprej manjši od konstanta krat f. Notacijo običajno uporabljamo za pozitivne funkcije.

Notacija se uporablja za izražanje računske zahtevnosti algoritmov.

Namesto f(n) \in O(g(n)) pogosto pišemo f(n) = O(g(n)). V tem primeru moramo upoštevati, da znak = ne pomeni enakosti funkcij. Pogosto se uporablja tudi zapis f(n) = h(n) + O(g(n)), ki pomeni, da je razlika med f(n) in h(n) v razredu O(g(n)).

Primer

Funkcija f(n) = 6n2 + 3n + 5 je v razredu O(n2), ker velja 6n2 + 3n + 5 < = 7n2 za n > = 5. Prav tako je f v razredu O(n3), saj notacija O predpisuje le zgornjo mejo.

Glej tudi

Povezave

Osebna orodja