Ordo

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 betyder O(n²) eller O(n³) att den största betydande termen är n² eller n³. Inom datavetenskap, särskilt komplexitetsteori, används det för att beskriva algoritmers effektivitet.

Definition

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

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

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

Generellt

$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})$ då $z = x^b.$

Exempelvis när man gör maclaurinutveckling av funktionen $\sin x^2$ till 4:e ordningen.

$\sin x^2 = x^2 - \frac{(x^2)^3}{3!} + O((x^2)^5) = x^2 - \frac{x^5}{3!} + O((x^7)$ då $x \rightarrow 0 .\$

Multiplikation

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

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 att $(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

Subtraktion av stora ordo ger

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

Eftersom att $\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

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

• Ordo (tidning), var en vetenskaplig tidskift utgiven av Lunds universitet.