Stor O-notasjon

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

Fordelen med en slik notasjon, er at det går an å forenkle kompleksitetsanalysen, uten å få alt for store feil. For eksempel er , da 100x2 er forsvinnende liten i forhold til x3 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 , sier vi at .

Relaterte notasjonerRediger

Notasjon Definisjon Matematisk definisjon Alternativ definisjon
  asymptotisk øvre grense    
  asymptotisk nedre grense    
  asymptotisk tett grense    
  asymptotisk neglisjerbar    
  asymptotisk dominerende    


Vanlige klasser av funksjonerRediger

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.