Ordo

Från Wikipedia
Hoppa till: navigering, sök
Se även ordo (palats).

Ordo (latin för ordning) är ett begrepp inom matematik och datavetenskap och används för ge ett mått på hur tung en term är. Till exempel betecknar O(n2) och O(en) något som växer lika fort som n2 respektive en då n ökar. Inom datavetenskap, särskilt komplexitetsteori, används det för att beskriva algoritmers effektivitet.

Definition[redigera | redigera wikitext]

Stora ordo definieras som  b(x) \cdot x^a = O(x^a), där  b(x) är en begränsad funktion i en omgivning nära origo.

Lilla ordo definieras som  b(x) \cdot x^a = o(x^a), där  b(x) \rightarrow 0 i en omgivning nära origo. Värt att notera är att lilla ordo kan ses som ett specialfall av stora ordo.

Användningsområden[redigera | redigera wikitext]

Inom matematik används ordo för olika typer av uppskattningar. Stora ordo används för att bestämma förkortade Taylorserier som är centralt vid beräkning av gränsvärden. Ordo används där för att bestämma resttermen. Med ökande ordo minskar felet vilket innebär att man kan utveckla någonting till önskad felmarginal. (Forsling och Neymark 2004. Matematisk analys, en variabel). Om vi tar funktionen  \cos (x) till exempel:

 \cos (x) = 1 - \frac{x^2}{2!} + \frac{x^4}{4!} + O(x^6)

Detta kan alltså tolkas som att  \cos (x) - (1 - \frac{x^2}{2!}  + \frac{x^4}{4!}) = O(x^6) , där O(x^6) blir felmarginalen, alltså hur nära det faktiska värdet man är.

Lilla ordo kan användas för att beskriva differentierbarhetsrelationen för funktioner med flera variabler (Böiers och Persson 2005. Analys i flera variabler).

Räkneregler för ordo[redigera | redigera wikitext]

Värt att notera är att både lilla och stora ordo har samma räkneregler.

Generellt[redigera | redigera wikitext]

 O(c \cdot x^a)  = O(x^a) , där c är en konstant.
  \lim_{x \to 0} O(x^a) \rightarrow 0 , där a > 0.
  \lim_{x \to 0} O(x^a) \rightarrow \infty , där a < 0.

Generellt gäller även att

 O(z^a) = O(x^{a+b})z = x^b.

Exempelvis när man gör maclaurinutveckling av funktionen sin x² till 4:e ordningen.

\sin x^2 = x^2 - \frac{(x^2)^3}{3!} + O((x^2)^5) = x^2 - \frac{x^6}{3!} + O(x^{10}) x \rightarrow 0 .\

Multiplikation[redigera | redigera wikitext]

Under förutsättningen att x är nära 0 tillämpas följande räkneregler:

 O(x^a) \cdot O(x^b) = O(x^{a+b})
 x^b \cdot O(x^a) = O(x^{a+b})
   c \cdot O(x^a) = O(x^a)

Detta medför att

 - O(x^a) = O(x^a) \,

eftersom man kan skriva  c = -1

Addition[redigera | redigera wikitext]

Addition av stora ordo ger

 O(x^a) + O(x^b) = O(x^a), \ a \le b , = b_1(x) \ x^a + b_2(x) \ x^b = x^a (b_1(x) + b_2(x) \  x^{b-a})

Eftersom  (b_1(x) + b_2(x)x^{b-a}) är en begränsad funktion leder det till att  x^b innesluts i x^a

Subtraktion[redigera | redigera wikitext]

Subtraktion av stora ordo ger

 O(x^a) - O(x^b) = O(x^a), a < b

Eftersom \Delta_1 ger att O(x^a) + (-1) \cdot O(x^b) = O(x^a) + O(x^b) = O(x^a), \ a < b

Värt att notera är att differensen när b = a inte är 0.

 O(x^a) - O(x^a) = O(x^a)

Detta kan förklaras på samma sätt som ovan:

 O(x^a) - O(x^a) = O(x^a) + (-1) \cdot O(x^a) = O(x^a) (Forsling och Neymark 2004. Matematisk analys, en variabel).

Relaterade notationer[redigera | redigera wikitext]

Notation I ord Definition
f(n) \in \mathcal{O}(g(n)) f växer högst lika snabbt som g \exists (C>0), n_0 : \forall(n>n_0) \; |f(n)| < |Cg(n)|
f(n) \in \Omega(g(n)) f växer minst lika snabbt som g \exists (C>0), n_0 : \forall (n>n_0) \; |Cg(n)| < |f(n)|
f(n) \in \Theta(g(n)) f växer lika snabbt som g \exists (C,C'>0), n_0 : \forall (n>n_0) \; |Cg(n)| < |f(n)| < |C'g(n)|
f(n) \in o(g(n)) f växer långsammare än g \forall (C>0),\exists n_0 : \forall(n>n_0) \; |f(n)| < |Cg(n)|
f(n) \in \omega(g(n)) f växer snabbare än g \forall (C>0),\exists n_0 : \forall(n>n_0) \; |Cg(n)| < |f(n)|
f(n) \sim g(n) asymptotiskt lika \lim_{n \to \infty} \frac{f(n)}{g(n)} = 1

Se även[redigera | redigera wikitext]