Hopp til innhold

Stor O-notasjon

Fra Wikipedia, den frie encyklopedi

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 notasjoner

[rediger | rediger kilde]
Notasjon Definisjon Matematisk definisjon Alternativ definisjon
asymptotisk øvre grense
asymptotisk nedre grense
asymptotisk tett grense
asymptotisk neglisjerbar
asymptotisk dominerende


Vanlige klasser av funksjoner

[rediger | rediger kilde]

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.