Cota superior asintótica
De Wikipedia, la enciclopedia libre
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 las cotas asintóticas superior e inferior (notación Ω):
- f(x) = Θ(g(x)) si y solo si f(x) = O(g(x)) y f(x) = Ω(x)
Tabla de contenidos |
[editar] 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².
[editar] Ó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 y n el tamaño de la entrada):
| notación | nombre |
|---|---|
| O(1) | orden constante |
| O(log n) | orden logarítmico |
| O([log n]c) | orden polilogarítmico |
| O(n) | orden lineal |
| O(n · log n) | orden lineal logarítmico |
| O(n²) | orden cuadrático |
| O(nc) | orden polinómico |
| O(cn), n > 1 | orden exponencial |
| O(n!) | orden factorial |
| O(nn) | orden doblemente exponencial |
[editar] Véase también
[editar] Bibliografía
- Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
