Cota superior asintótica

De Wikipedia, la enciclopedia libre
Saltar a: navegación, búsqueda

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)), Orden de 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 , f(x) no sobrepasa a . 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.

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

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 en lugar de h(x)=x², siempre que esté claro cuál 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 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 Ω):

Propiedades[editar]

Sea , sean , , , funciones y 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[editar]

  • La función f(x) = x+10 puede ser acotada superiormente por la función g(x) = x². Para demostrarlo basta notar que para todo valor de x ≥ 3.7016, se cumple x+10 ≤ x². Por tanto x+10 = O(x²). Sin embargo, x² no sirve como cota inferior para x+10, es decir, .
    Observación: Este ejemplo muestra que el uso del símbolo "=" está mal empleado (matemáticamente) pues la notación de Landau (O grande) no es reflexiva.
  • La función 200x está acotada superiormente por . Quiere decir que cuando x tiende a infinito el valor de 200x se puede despreciar con respecto al de .

Órdenes usuales para funciones[editar]

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 sublogarítmico
O(log n) orden logarítmica
O(n · log n) orden lineal logarítmica
O() orden sublineal
O(n) orden lineal o de primer orden
O(n2) orden cuadrática o de segundo orden
O(n3), ... orden cúbica o de tercer orden, ...
O(nc) orden potencial fija
O(cn), n > 1 orden exponencial
O(n!) orden factorial
O(nn) orden potencial exponencial

Véase también[editar]

Bibliografía[editar]

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