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:
Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor x0 f(x) no sobrepasa a cg(x). 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 cg(x) con respecto a f(x) cuando x tiende a infinito.
La cota ajustada asintótica (notación ?) tiene relación con la las cotas superior e inferior asintóticas (notación ?):
- f(x) = ?(g(x)) si y solo si f(x) = O(g(x)) y f(x) = ?(x)
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) | ? |
Bibliografía
- Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
