Stor O-notasjon
Fra Wikipedia, den frie encyklopedi
Stor O-notasjon er et begrep som gir en asymptotisk tilnærming til en funksjon g(x), og skrives ofte O(g(x)). Det 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 
.
