Ordo

Från Rilpedia

Texten från svenska Wikipedia

Ordo (latin för ordning) är ett begrepp inom matematik och datavetenskap och används för att mäta 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.

Inom matematik används ordo för olika typer av uppskattningar. En funktion f(x) sägs vara "stort ordo" g(x) då x $\rightarrow$ 0 om f(x)/g(x) är begränsad då x $\rightarrow$ 0. Detta skrivs

f(x) = O(g(x)) då x $\rightarrow$ 0.

Ofta utelämnar man "x $\rightarrow$ 0" om det framgår av sammanhanget att det gäller i närheten av origo och skriver bara f(x) = O(g(x)).

f(x) sägs vara "litet ordo" g(x) då x $\rightarrow$ 0 om f(x)/g(x) $\rightarrow$ 0 då x $\rightarrow$ 0, vilket skrivs

f(x) = o(g(x)) då x $\rightarrow$ 0.

Ordobegreppet används i praktiska sammanhang vid Taylor- och Maclaurinutvecklingar som beteckning på resttermerna (Forsling och Neymark 2004. Matematisk analys, en variabel).

Exempel: sin(x) =1-x³/6+O(x⁵) då x $\rightarrow$ 0.

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)$ $˜$ $g (n)$	asymptotiskt lika	$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 1$