Usuari:Mcapdevila/Cota superior asimptòtica

En anàlisi d'algorismes una fita superior asimptòtica és una funció que serveix de cota superior d'una altra funció quan l'argument tendeix a infinit. Usualment es fa servir la notació de Landau O(g(x)) (o col·loquialment anomenada Notació O Gran) per referir-se a les funcions acotades superiorment per la funció g(x). Anomenada així per Edmund Landau qui va desenvolupar la teoria.

Més formalment es defineix:

$O(g(x))=\left\{{\begin{matrix}f(x):\exists c,\ \exists x_{0}>0\ \ {\mbox{tals que,}}\ \forall x\geq x_{0}\ {\mbox{es compleix}}\ 0\leq |f(x)|\leq c|g(x)|\end{matrix}}\right\}$

Una funció f ( x ) pertany a O ( g ( x )) quan hi ha una constant positiva c tal que a partir d'un valor $x_{0}$, f ( x ) no sobrepassa a $cg(x)$. Vol dir que la funció f és inferior a g a partir d'un valor donat excepte per un factor constant.

La cota superior asimptòtica té gran importància en Teoria de la complexitat computacional a l'hora de definir les classes de complexitat.

f (x) = O (g (x)) .

Tot i que O (g (x)) està definit com un conjunt, s'acostuma a escriure f (x) = O (g (x)) en comptes de f (x) ∈ O (g (x)). Moltes vegades també es parla d'una funció nomenant únicament la seva expressió, com en x ² en comptes de h (x) = x ² , sempre que estigui clar quin és el paràmetre de la funció dins de l'expressió. En la gràfica es dóna un exemple esquemàtic de com es comporta $cg(x)$ pel que fa a f (x) quan x tendeix a infinit. Note més que aquest conjunt és no buit doncs f (x) = O (g (x)) .

La cota ajustada asimptòtica (notació Θ) té relació amb les cotes asimptòtiques superior i inferior (notació Ω):

$f(x)=\Theta (g(x)){\mbox{si i només si}}f(x)=O(g(x)){\mbox{i}}f(x)=\Omega (g(x))\,$

Propietats

Sigui $I\subseteq \mathbb {R}$, siguin $f_{1}:I\to \mathbb {R}$, $g_{1}:I\to \mathbb {R}$, $F_{2}:I\to \mathbb {R}$, $g_{2}:I\to \mathbb {R}$ funcions i $k$ un real. Llavors els següents enunciats són certs

I) Si $f_{1}=O(g_{1})\,$ i $g_{1}=O(g_{2})\,$, aleshores $f_{1}=O(g_{2})\,$

Ii) Si $f_{1}=O(g_{1})\,$ i $F_{2}=O(g_{2})\,$, aleshores $f_{1}f_{2}=O(g_{1}g_{2})\,$

Iii) $f_{2}O(g_{1})=O(f_{2}g_{1})\,$ (aquí és igualtat entre conjunts)

Iv) Si $f_{1}=O(g_{1})\,$ i $F_{2}=O(g_{2})\,$, aleshores $f_{1}+F_{2}=O(|g_{1}|+|g_{2}|)\,$

V) Si $k\neq 0\,$ llavors $O(g_{1})=O(kg_{1})\,$ (aquí és igualtat entre conjunts)

Vi) Si $f_{1}=O(g_{1})\,$, aleshores $kf_{1}=O(g_{1})\,$.

Exemples

• La funció x+10 pot ser fitada superiorment per la funció 11x ² . Per demostrar prou notar que per a tot valor de x ≥ 1 es compleix x+10 ≤ 11x ² . Per tant x+10 = O (x ²) . No obstant això, x ² no serveix com a cota inferior per x+10 , és a dir, $11x^{2}$ ≠ $O(x+10)$.
  Observació: Aquest exemple mostra que l'ús del símbol "=" està mal emprat (matemàticament), ja que la notació de Landau (O gran) no és reflexiva.
• La funció x ²+200x està fitada superiorment per x ² . Vol dir que quan x tendeix a infinit el valor de 200x es pot menysprear pel que fa al de x ² .

Ordres usuals per a funcions

Els ordres més utilitzats en anàlisi d'algorismes, en ordre creixent, són els següents (on c representa una constant i n la mida de l'entrada):

notació	nom
O (1)	Ordre constant
O (log log n )	Ordre subalgorítmic
O (log n )	Ordre logarítmic
O (${\sqrt {n}}$)	Ordre sublineal
O ( n )	Ordre lineal
O ( n · log n )	Ordre lineal logarítmic
O ( n c )	Ordre polinòmic o potencial
O ( c n ), n> 1	Ordre exponencial
O ( n ! )	Ordre factorial

Vegeu també

• Cota inferior asimptòtica
• Cota ajustada asimptòtica
• Notació de Landau

Bibliografia

• Introduction to Algorithms, Second Edition by Thomas H. Corman, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein