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)) (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:

O(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existen } c,x_0>0\mbox{ tales que} \\ \forall x\ge x_0: 0\le |f(x)|\le c|g(x)| \end{matrix}\right\}

Una función f(x) pertenece a O(g(x)) cuando existe una constante positiva c tal que a partir de un valor x_0, 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.

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 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 Ω):

f(x)=\Theta(g(x)) \mbox{ si y solo si } f(x)=O(g(x)) \mbox{ y } f(x)=\Omega(g(x))\,

Propiedades[editar]

Sea E\subseteq \mathbb{R}, sean f_1:E\to \mathbb{R}, g_1:E\to \mathbb{R}, f_2:E\to \mathbb{R}, g_2:E\to \mathbb{R} funciones y k un real. Entonces los siguientes enunciados son ciertos

i) Si f_1 = O(g_1)\, y g_1 = O(g_2)\,, entonces f_1 = O(g_2)\,
ii) Si f_1=O(g_1)\, y f_2=O(g_2)\,,entonces f_1f_2=O(g_1g_2)\,
iii) f_2O(g_1)=O(f_2g_1)\, (aquí es igualdad entre conjuntos)
iv) Si f_1=O(g_1)\, y f_2=O(g_2)\,,entonces f_1+f_2=O(|g_1|+|g_2|)\,
v) Si k\neq 0\, entonces O(g_1)=O(kg_1)\, (aquí es igualdad entre conjuntos)
vi) Si f_1= O(g_1)\,, entonces kf_1=O(g_1)\,.

Ejemplos[editar]

  • 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, no sirve como cota inferior para x+10, es decir, 11x^2O(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 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ítmico
O(\sqrt n) 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[editar]

Bibliografía[editar]

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