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 betecknar O(n²) och O(eⁿ) något som växer lika fort som n² respektive eⁿ då n ökar. 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, och gör en Maclaurinutveckling:

$\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})$. I detta fall visar termen att skillnaden mellan polynomutvecklingen och funktionen i närheten av x=0 växer som x⁶. Den säger dock inget om hur stor skillnaden faktiskt är; den skulle kunna vara mycket liten eller helt dominerande.

Lilla ordo kan användas för att beskriva differentierbarhetsrelationen för funktioner med 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\cdot b})$ då $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})$ 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\leq 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

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})$ .

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 tidskrift utgiven av Teknologkåren vid Lunds Tekniska Högskola.