Redigerer Stor O-notasjon

'''Stor O-notasjon''' er en matematisk notasjon som gir en [[asymptote|asymptotisk]] tilnærming til en funksjon <math>g(x)</math>, og skrives ofte <math> O(g(x))</math>. Formålet er å kunne gi en enkel og grov beskrivelse av utviklingen til funksjonen <math>g(x)</math> når x øker. Mer presist blir symbolet <math>O</math> 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 [[informatikk]]en som sier noe om ressursbruken til en [[algoritme]].

Uttrykket <math>\ f(x)=O(g(x))</math>, eventuelt <math>\ f \in O(g)</math>, betyr at <math>\ f(x)</math> for store verdier av <math>\ x </math> alltid er mindre enn <math>\ cg(x)</math>, der ''c'' er en konstant. En annen måte å skrive det på, er 

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

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

==Relaterte notasjoner==

{| class="wikitable"
!Notasjon
!Definisjon
!Matematisk definisjon
!Alternativ definisjon
|-
|<math>f(n) \in O(g(n))</math>
|asymptotisk øvre grense
|<math>\limsup_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| < \infty</math>
|<math>\exists \;x_0,\exists \;M>0\mbox{ slik at } |f(x)| \le \; M |g(x)|\mbox{ for alle }x>x_0.</math>
|-
|<math>f(n) \in \Omega(g(n))</math>
|asymptotisk nedre grense
|<math>\liminf_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| > 0 </math>
|<math>\exists \;x_0,\exists \;M>0\mbox{ slik at } |f(x)| \ge \; M |g(x)|\mbox{ for alle }x>x_0.</math>
|-
|<math>f(n) \in \Theta(g(n))</math>
|asymptotisk tett grense
|<math>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</math>
|<math>f(n) \in O(g(n)) \mbox{ og } f(n) \in \Omega(g(n))</math>
|-
|<math>f(n) \in o(g(n))</math>
|asymptotisk neglisjerbar
|<math>\lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = 0</math>
|<math>\forall M>0 \; \exists \;x_0 \mbox{ slik at } |f(x)| < \; M |g(x)| \mbox{ for alle }x>x_0.</math>
|-
|<math>f(n) \in \omega(g(n))</math>
|asymptotisk dominerende
|<math>\lim_{n \to \infty} \left|\frac{f(n)}{g(n)}\right| = \infty</math>
|<math>\forall M \; \exists \;x_0 \mbox{ slik at } |f(x)| > \; M |g(x)| \mbox{ for alle }x>x_0.</math>
<!-- Sometimes this is expressed as "\forall M<\infty" – any preference here? -->
|}



== 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.

{| class="wikitable"
!Notatsjon                   !! Navn  !! Eksempel
|-
|''O''(1)                                 || konstant               || Avgjør om et tall er et partall eller oddetall.
|-
|''O''(log ''n'')                         || [[logaritme|logaritmisk]] || Finn et element i en sortert liste [[binærsøk]].
|-
|''O''(''n'')                             || [[linearitet|lineær]]                || Finn et element i en usortert liste.
|-
|''O''(''n'' log ''n'')                   || loglineær                 || Sorter en liste med [[heapsort]].
|-
|''O''(''n''<sup>2</sup>)                 || kvadratisk                || Sorter en liste med [[insertion sort]].
|-
|''O''(''c''<sup>''n''</sup>)             || [[Eksponensialfunksjon|eksponensiell]]         || Finn den eksakte løsningen til [[traveling salesman]]-problemet.
|-
|''O''(''n''!)                            || [[Kombinatorikk|kombinatorisk]]  || Prøv alle mulige [[permutasjon]]er.
|}
{{Autoritetsdata}}

[[Kategori:Algoritmer‎]]
[[Kategori:Matematisk notasjon]]