Stor O-notasjon

Fra Wikipedia, den frie encyklopedi

Gå til: navigasjon, søk

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

\limsup_{x \to \infty} \left|\frac{f(x)}{g(x)}\right|<\infty.

Fordelen med en slik notasjon, er at det går an å forenkle kompleksitetsanalysen, uten å få alt for store feil. For eksempel er x^3 + 100x^2 \in O(x^3), 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 f \in O(g), g\in O(f), sier vi at f \in \Theta(g).

[rediger] Relaterte notasjoner

Notasjon Definisjon Matematisk definisjon Alternativ definisjon
f(n) \in O(g(n)) asymptotisk øvre grense \limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| < \infty \exists \;x_0,\exists \;M>0\mbox{ slik at } |f(x)| \le \; M |g(x)|\mbox{ for alle }x>x_0.
f(n) \in \Omega(g(n)) asymptotisk nedre grense \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0 \exists \;x_0,\exists \;M>0\mbox{ slik at } |f(x)| \ge \; M |g(x)|\mbox{ for alle }x>x_0.
f(n) \in \Theta(g(n)) asymptotisk tett grense 0 < \liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| \leq \limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right|< \infty f(n) \in O(g(n)) \mbox{ og } f(n) \in \Omega(g(n))
f(n) \in o(g(n)) asymptotisk neglisjerbar \lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = 0 \forall M>0 \; \exists \;x_0 \mbox{ slik at } |f(x)| < \; M |g(x)| \mbox{ for alle }x>x_0.
f(n) \in \omega(g(n)) asymptotisk dominerende \lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = \infty \forall M \; \exists \;x_0 \mbox{ slik at } |f(x)| > \; M |g(x)| \mbox{ for alle }x>x_0.


[rediger] 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 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.
Hentet fra «http://no.wikipedia.org/wiki/Stor_O-notasjon»
Personlige verktøy