Stor O-notasjon

Stor O-notasjon er en matematisk notasjon som gir en asymptotisk tilnærming til en funksjon $g(x)$, og skrives ofte $O(g(x))$. Formålet er å kunne gi en enkel og grov beskrivelse av utviklingen til funksjonen $g(x)$ når x øker. Mer presist blir symbolet $O$ brukt til å beskrive en asymptotisk øvre grense for en funksjon ved hjelp av en, som oftest, enklere funksjon. Det er også andre symboler o, Ω, ω, and Θ for å beskrive forskjellige andre asymptotiske grenser. Stor O-notasjon blir spesielt brukt i kompleksitetsteori, en del av informatikken som sier noe om ressursbruken til en algoritme.

Uttrykket $\ f(x)=O(g(x))$, eventuelt $\ f\in O(g)$, betyr at $\ f(x)$ for store verdier av $\ x$ alltid er mindre enn $\ cg(x)$, der c er en konstant. En annen måte å skrive det på, er

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

Fordelen med en slik notasjon, er at det går an å forenkle kompleksitetsanalysen, uten å få alt for store feil. For eksempel er $x^{3}+100x^{2}\in O(x^{3})$, da 100x² er forsvinnende liten i forhold til x³ når x er stor.

Grensen er ikke streng; g kan godt vokse mye raskere enn f. Hvis de vokser like raskt, det vil si at $f\in O(g),g\in O(f)$, sier vi at $f\in \Theta (g)$.

Relaterte notasjoner

Notasjon	Definisjon	Matematisk definisjon	Alternativ definisjon
$f(n)\in O(g(n))$	asymptotisk øvre grense	$\limsup _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|<\infty$	$\exists \;x_{0},\exists \;M>0{\mbox{ slik at }}|f(x)|\leq \;M|g(x)|{\mbox{ for alle }}x>x_{0}.$
$f(n)\in \Omega (g(n))$	asymptotisk nedre grense	$\liminf _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|>0$	$\exists \;x_{0},\exists \;M>0{\mbox{ slik at }}|f(x)|\geq \;M|g(x)|{\mbox{ for alle }}x>x_{0}.$
$f(n)\in \Theta (g(n))$	asymptotisk tett grense	$0<\liminf _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|\leq \limsup _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|<\infty$	$f(n)\in O(g(n)){\mbox{ og }}f(n)\in \Omega (g(n))$
$f(n)\in o(g(n))$	asymptotisk neglisjerbar	$\lim _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|=0$	$\forall M>0\;\exists \;x_{0}{\mbox{ slik at }}|f(x)|<\;M|g(x)|{\mbox{ for alle }}x>x_{0}.$
$f(n)\in \omega (g(n))$	asymptotisk dominerende	$\lim _{n\to \infty }\left|{\frac {f(n)}{g(n)}}\right|=\infty$	$\forall M\;\exists \;x_{0}{\mbox{ slik at }}|f(x)|>\;M|g(x)|{\mbox{ for alle }}x>x_{0}.$

Vanlige klasser av funksjoner

Her er en liste over klasser av funksjoner som en ofte støter på ved analyse av algoritmer. De beskriver tidsforbruket til algoritmer når n øker mot uendelig. Funksjonene er listet med økende kompleksitet. c er en vilkårlig konstant.

Notatsjon	Navn	Eksempel
O(1)	konstant	Avgjør om et tall er et partall eller oddetall.
O(log n)	logaritmisk	Finn et element i en sortert liste binærsøk.
O(n)	lineær	Finn et element i en usortert liste.
O(n log n)	loglineær	Sorter en liste med heapsort.
O(n2)	kvadratisk	Sorter en liste med insertion sort.
O(cn)	eksponensiell	Finn den eksakte løsningen til traveling salesman-problemet.
O(n!)	kombinatorisk	Prøv alle mulige permutasjoner.