Stor O-notasjon

Stor O-notasjon er en matematisk notasjon som gir en asymptotisk tilnærming til en funksjon ${\displaystyle g(x)}$, og skrives ofte ${\displaystyle O(g(x))}$. Formålet er å kunne gi en enkel og grov beskrivelse av utviklingen til funksjonen ${\displaystyle g(x)}$ når x øker. Mer presist blir symbolet ${\displaystyle 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 ${\displaystyle \ f(x)=O(g(x))}$, eventuelt ${\displaystyle \ f\in O(g)}$, betyr at ${\displaystyle \ f(x)}$ for store verdier av ${\displaystyle \ x}$ alltid er mindre enn ${\displaystyle \ cg(x)}$, der c er en konstant. En annen måte å skrive det på, er

${\displaystyle \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 ${\displaystyle 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 ${\displaystyle f\in O(g),g\in O(f)}$, sier vi at ${\displaystyle f\in \Theta (g)}$.

Relaterte notasjoner

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