Cota superior asintótica
En análisis de algoritmos una cota superior asintótica es una función que sirve de cota superior de otra función cuando el argumento tiende a infinito. Usualmente se utiliza la notación O(g(x)) para referirse a las funciones acotadas superiormente por la función g(x).
Más formalmente se define:
- <math>O(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existen } c,x_0 \mbox{ constantes positivas tales que} \\ \forall x:x_0\le x: 0\le f(x)\le cg(x) \end{matrix}\right\}</math>
Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor <math>x_0</math> f(x) no sobrepasa a <math>cg(x)</math>. Quiere decir que la función f es inferior a g a partir de un valor dado salvo por una factor constante.
La cota superior asintótica tiene gran importancia en Teoría de la complejidad computacional a la hora de definir las clases de complejidad.
A pesar de que O(g(x)) está definido como un conjunto, se acostumbra escribir f(x)=O(g(x)) en lugar de f(x)∈O(g(x)). Muchas veces también se habla de una función nombrando únicamente su expresión, como en x² en lugar de h(x)=x², siempre que esté claro cual es el parámetro de la función dentro de la expresión. En la gráfica se da un ejemplo esquemático de como se comporta <math>cg(x)</math> con respecto a f(x) cuando x tiende a infinito.
La cota ajustada asintótica (notación Θ) tiene relación con las cotas superior e inferior asintóticas (notación Ω):
- <math>f(x)=\Theta(g(x)) \mbox{ si y solo si } f(x)=O(g(x)) \mbox{ y } f(x)=\Omega(x)</math>
Tabla de contenidos |
Ejemplos
- La función x+10 puede ser acotada superiormente por la función x². Para demostrarlo basta notar que para todo valor de x≥1 se cumple x+10≤11x². Por tanto x+10 = O(x²) (sin embargo, x² no sirve como cota inferior para x+10).
- La función x²+200x está acotada superiormente por x². Quiere decir que cuando x tiende a infinito el valor de 200x se puede despreciar con respecto al de x².
Órdenes usuales para funciones
Los órdenes más utilizados en análisis de algoritmos, en orden creciente, son los siguientes (donde c representa una constante):
| notación | nombre |
|---|---|
| O(1) | orden constante |
| O(log x) | orden logarítmico |
| O([log x]c) | orden polilogarítmico |
| O(x) | orden lineal |
| O(x · log x) | orden lineal logarítmico |
| O(x²) | orden cuadrático |
| O(xc) | orden polinómico |
| O(cx) | orden exponencial |
| O(x!) | orden factorial |
| O(xx) | orden exponencial |
Bibliografía
- Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Categorías
Análisis matemático | Complejidad computacional