O notacija

O notacija (tudi notacija veliki O) se v matematiki uporablja za opisovanje limitnega obnašanja funkcije, ko argument gre proti določeni vrednosti ali neskončnosti. Ta notacija pripada večji družini notacij, ki jih imenujemo Landauova notacija, Bachmann-Landauova notacija (imenovana po Edmundu Landau (1877 – 1938) in Paulu Bachmannu (1837 - 1920)) ali asimptotska notacija.

V računalništvu se notacija O uporablja za razvrščanje algoritmov po tem kako se odzivajo na spremembe v velikosti vhoda.

Naj bosta f(x) in g(x) dve funkciji, ki sta definirani nad neko podmnožico realnih števil. Lahko zapišemo :

${\displaystyle f(x)=O(g(x)){\text{ ko gre }}x\to \infty \,}$

Če in samo, če obstoja pozitivna konstanta M tako, da je za vse dovolj velike vrednosti x , je f(x) kvečjemu z M pomnožen z g(x) v absolutno vrednost. To je f(x) = O(g(x)) samo, če in samo če obstoja pozitivno realno število M in realno število x₀, da velja

${\displaystyle |f(x)|\leq \;M|g(x)|{\text{ za vse }}x>x_{0}}$.

V mnogih primerih je predpostavka, da nas zanima samo stopnja rasti ko gre x proti neskončnosti, neveljavna. Običajno zapišemo f(x) = O(g(x)). Označevanje se lahko uporabi za prikaz obnašanja funkcije f blizu nekega realnega števila (pogosto okoli a=0). Lahko zapišemo, da je

${\displaystyle f(x)=O(g(x)){\text{ kadar gre }}x\to a\,}$

če in samo, če obstoja takšni pozitivni števili δ in M, da velja

${\displaystyle |f(x)|\leq \;M|g(x)|{\text{ za }}|x-a|<\delta }$.

Če je g(x) neničelen za vrednosti dovolj blizu vrednosti a se lahko obe od teh definicij združita z uporabo zgornje in spodnje limite

${\displaystyle f(x)=O(g(x)){\text{ kadar gre }}x\to a\,}$

če in samo, če je

${\displaystyle \limsup _{x\to a}\left|{\frac {f(x)}{g(x)}}\right|<\infty }$.

notacija	ime	opis	definicija: za dovolj velike ${\displaystyle n}$...	definicija	opombe
${\displaystyle f(n)\in O(g(n))}$	veliki omikron; veliki O; veliki Oh	${\displaystyle f}$ je omejena zgoraj z ${\displaystyle g}$ (do konstantnega faktorja) asimptotično	${\displaystyle |f(n)|\leq g(n)\cdot k}$ za neki k	${\displaystyle \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq |g(n)\cdot k|}$ ali ${\displaystyle \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;f(n)\leq g(n)\cdot k}$
${\displaystyle f(n)\in \omega (g(n))}$	veliki omega	${\displaystyle f}$ je omejen spodaj z ${\displaystyle g}$ (do konstatnega faktorja) asimptotično	${\displaystyle f(n)\geq g(n)\cdot k}$ za pozitivni k	${\displaystyle \exists k>0\;\exists n_{0}\;\forall n>n_{0}\;g(n)\cdot k\leq f(n)}$	od začetka 20. stoletja so dokumenti o teoriji števil so stalno bolj uporabljali to notacijo, vendar z občutkom, da je f = o(g) napačno.
${\displaystyle f(n)\in \theta (g(n))}$	veliki theta	${\displaystyle f}$ je omejen zgoraj in spodaj z ${\displaystyle g}$ asimptotično	${\displaystyle g(n)\cdot k_{1}\leq f(n)\leq g(n)\cdot k_{2}}$ za neki pozitivni k1, k2	${\displaystyle \exists k_{1}>0\;\exists k_{2}>0\;\exists n_{0}\;\forall n>n_{0}}$ ${\displaystyle g(n)\cdot k_{1}\leq f(n)\leq g(n)\cdot k_{2}}$
${\displaystyle f(n)\in o(g(n))}$	mali omikron; mali O; mali Oh	${\displaystyle f}$ prevladuje ${\displaystyle g}$ asimptotično	${\displaystyle |f(n)|\leq |g(n)|\cdot \varepsilon }$ za vsak ${\displaystyle \varepsilon }$	${\displaystyle \forall \varepsilon >0\;\exists n_{0}\;\forall n>n_{0}\;|f(n)|\leq |g(n)\cdot \varepsilon |}$
${\displaystyle f(n)\in \omega (g(n))}$	mali omega	${\displaystyle f}$ prevladuje ${\displaystyle g}$ asimptotsko	${\displaystyle f(n)\geq g(n)\cdot k}$ za vsak k	${\displaystyle \forall k>0\;\exists n_{0}\;\forall n>n_{0}\;g(n)\cdot k<f(n)}$
${\displaystyle f(n)\sim g(n)\!}$	On the order of	${\displaystyle f}$ je enak ${\displaystyle g}$ asimptotsko	${\displaystyle f(n)/g(n)\to 1}$	${\displaystyle \forall \varepsilon >0\;\exists n_{0}\;\forall n>n_{0}\;\left|{f(n) \over g(n)}-1\right|<\varepsilon }$

Bachmann–Landauova notacija uporablja nekaj mnemotehnik. Tako lahko preberemo "omikron" kot "o-mikron" in "omega" lahko preberemo kot "o-mega".

• mnemotehnika za o-micron: Čitanje o-mikron ${\displaystyle f(n)\in O(g(n))}$ in ${\displaystyle f(n)\in o(g(n))}$ si lahko mislimo kot "O-manjši kot" in "o-manjši kot". Ta mnemotehnika micro/manjši se nanaša na dovolj velik vhodni parameter ali parametre, ${\displaystyle f}$ raste po stopnji, ki je manjša kot ${\displaystyle cg}$ glede na ${\displaystyle g\in O(f)}$ or ${\displaystyle g\in o(f)}$.
• mnemotehnika za o-mega : Čitanje o-mega ${\displaystyle f(n)\in \Omega (g(n))}$ in ${\displaystyle f(n)\in \omega (g(n))}$ si lahko mislimo kot "O-večji kot". Ta mnemotehnika mega/večji: se nanaša na dovolj velik vhodni parameter ali parametre, ${\displaystyle f}$ raste po stopnji, ki je večja kot ${\displaystyle cg}$ glede na ${\displaystyle g\in \Omega (f)}$ ali ${\displaystyle g\in \omega (f)}$.
• mnemotehnika za zgornji znak: Ta mnemotehnika nas spominja na to, kdaj uporabimo zgornje grške črke v ${\displaystyle f(n)\in O(g(n))}$ in ${\displaystyle f(n)\in \Omega (g(n))}$: za dovolj velik vhodni parameter ali parametre, ${\displaystyle f}$ raste po stopnji, ki bi lahko bila enaka z ${\displaystyle cg}$ glede na ${\displaystyle g\in O(f)}$.
• mnemotehnika za spodnji znak: Ta mnemotehnika nas spominja na to, kdaj moramo uporabiti male grške črke v ${\displaystyle f(n)\in o(g(n))}$ in ${\displaystyle f(n)\in \omega (g(n))}$: za dovolj velik vhodni parameter ali parametre, ${\displaystyle f}$ raste po stopnji, ki je neenaka z ${\displaystyle cg}$ glede na ${\displaystyle g\in O(f)}$.

Razen notacije O se v računalništvu uporablja še notacija z velikim teta (Θ) in velikim omega (Ω) . V računalništvu pa se zelo redko uporablja notacija z uporabo malega omega (ω).

• Notacija „veliki O“ na MaFiRa Arhivirano 2008-12-06 na Wayback Machine. (slovensko)
• Uvod v asimptotske notacije Arhivirano 2012-07-22 na Wayback Machine. (angleško)
• Landauovi simboli na MathWorld (angleško)