Cota superior asintòtica

En anàlisis d'algoritmes, una cota superior asintòtica és una funció que servix de cota superior d'una atra funció quan l'argument tendix a infinit. Usualment s'utilisa la notació de Landau: O(g(x)), Orde de g(x), coloquialment cridada Notació O Gran, per a referir-se a les funcions acotades superiorment per la funció g(x).

Formalment es definix:

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

La cota superior asintòtica té gran importància en la Teoria de la complexitat computacional quan es definixen les classes de complexitat.

Archiu:CotaSuperiorAsintotica.png

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

A pesar de que O(g(x)) està definida com un conjunt, s'acostuma escriure f(x)=O(g(x)) en lloc de f(x)∈O(g(x)), ya que la classe d'equivalència de f coincidix en el conjunt O(g(x)). Moltes voltes també es parla de la funció nomenant únicament la seua expressió, com en x² en lloc de h(x)=x², sempre que estiga clar quin és el paràmetro de la funció dins de l'expressió. En la gràfica es dona un eixemple esquemàtic de cóm es comporta $c g (x)$ sobre f(x) quan x tendix a infinit. Note's ademés que dit conjunt és no buit puix g(x)=O(g(x)).

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

Propietats

Siga $E \subseteq ℝ$ , siguen $f_{1} : E \to ℝ$ , $g_{1} : E \to ℝ$ , $f_{2} : E \to ℝ$ , $g_{2} : E \to ℝ$ 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})

, llavors

f_{1} = O (g_{2})

ii) Si

f_{1} = O (g_{1})

i

f_{2} = O (g_{2})

,llavors

f_{1} f_{2} = O (g_{1} g_{2})

iii)

f_{2} O (g_{1}) = O (f_{2} g_{1})

(ací és igualtat entre conjunts)

iv) Si

f_{1} = O (g_{1})

i

f_{2} = O (g_{2})

, llavors

f_{1} + f_{2} = O {m a x (| g_{1} |, | g_{2} |)}

v) Si

k \neq 0

llavors

O (g_{1}) = O (k g_{1})

(ací és igualtat entre conjunts)

vaig vore) Si

f_{1} = O (g_{1})

, llavors

k f_{1} = O (g_{1})

.

Eixemples

La funció f(x) = x+10 pot ser acotada superiorment per la funció g(x) = x². Per a demostrar-ho basta notar que para tot valor de x ≥ 3.7016, es complix x+10 ≤ x². Per tant x+10 = O(x²). No obstant, x² no servix com a cota inferior per a x+10, és dir, $x^{2} \neq ◯ (x + 10)$ .
Observació: Este eixemple mostra que $f = O (g)$ no implica $g = O (f)$ , és dir, la relació entre funcions donada per la notació de Landau no és simètrica. No obstant, sí és reflexiva: $f = O (f)$
La funció 200x està acotada superiorment per x². Vol dir que quan x tendix a infinit el valor de 200x es pot despreciar sobre el de x².

Vore també

Bibliografia

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

Este artícul conté una traducció derivada de «Cota superior asintótica» de Wikipedia en castellà publicada baix la Llicència de documentació lliure de GNU i la Llicència Creative Commons Reconeiximent-CompartirIgual 4.0 Internacional.