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