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 notasjoner

NotasjonDefinisjonMatematisk definisjonAlternativ definisjonasymptotisk øvre grenseasymptotisk nedre grenseasymptotisk tett grenseasymptotisk neglisjerbarasymptotisk dominerende

 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   EksempelO(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.

Kategori:Algoritmer‎
Kategori:Matematisk notasjon