- 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 de Landau O(g(x)) (o coloquialmente llamada Notación O Grande) 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 un 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. Note además que dicho conjunto es no vacío pues f(x)=O(g(x)).
La cota ajustada asintótica (notación Θ) tiene relación con las cotas asintóticas superior e inferior (notación Ω):
Contenido
Propiedades
Sea , sean , , , funciones y k un real. Entonces los siguientes enunciados son ciertos
- i) Si y , entonces
- ii) Si y ,entonces
- iii) (aquí es igualdad entre conjuntos)
- iv) Si y ,entonces
- v) Si entonces (aquí es igualdad entre conjuntos)
- vi) Si , entonces .
Ejemplos
- La función x+10 puede ser acotada superiormente por la función 11x². 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, es decir, 11x2≠O(x + 10).
Observación: Este ejemplo muestra que el uso del símbolo "=" esta mal empleado (matemáticamente) pues la notación de Landau (O grande) no es reflexiva. - 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 y n el tamaño de la entrada):
notación nombre O(1) orden constante O(log log n ) orden subalgorítmico O(log n) orden logarítmico O() orden sublineal O(n) orden lineal O(n · log n) orden lineal logarítmico O(nc) orden potencial O(cn), n > 1 orden exponencial O(n!) orden factorial O(nn) orden potencial exponencial[cita requerida] Véase también
Bibliografía
- Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
- i) Si y , entonces
Wikimedia foundation. 2010.