Cota superior asintótica

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:

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 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.

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

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

Contenido

Propiedades

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

  • 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(\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

Bibliografía

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

Wikimedia foundation. 2010.

Игры ⚽ Нужен реферат?

Mira otros diccionarios:

  • 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 O(g(x)) para referirse a las funciones acotadas… …   Enciclopedia Universal

  • Cota ajustada asintótica — Saltar a navegación, búsqueda En análisis de algoritmos una cota ajustada asintótica es una función que sirve de cota tanto superior como inferior de otra función cuando el argumento tiende a infinito. Usualmente se utiliza la notación Θ(g(x))… …   Wikipedia Español

  • Cota inferior asintótica — En análisis de algoritmos una cota inferior asintótica es una función que sirve de cota inferior de otra función cuando el argumento tiende a infinito. Usualmente se utiliza la notación Ω(g(x)) para referirse a las funciones acotadas… …   Wikipedia Español

  • Cota inferior asintótica — En análisis de algoritmos una cota inferior asintótica es una función que sirve de cota inferior 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… …   Enciclopedia Universal

  • Cota ajustada asintótica — En análisis de algoritmos una cota ajustada asintótica es una función que sirve de cota tanto superior como inferior de otra función cuando el argumento tiende a infinito. Usualmente se utiliza la notación T(g(x)) para referirse a las funciones… …   Enciclopedia Universal

  • Cota (desambiguación) — Saltar a navegación, búsqueda Cota puede significar: Lugares Cota, un municipio de Cundinamarca, Colombia. Cota, una freguesia portuguesa del concelho de Viseu. Objetos Cota de malla, prenda de la armadura medieval. Cota superior asintótica,… …   Wikipedia Español

  • Serie asintótica — En matemáticas, una expansión asintótica o serie asintótica o serie de Poincaré es una serie formal de funciones tal que converge asintóticamente a una función dada, esto significa que si cortamos la serie se obtiene una aproximación de la… …   Wikipedia Español

  • Notación de Landau — En matemática, la Notación de Landau, también llamada o minúscula y O mayúscula , es una notación para la comparación asintótica de funciones, lo que permite establecer la cota inferior asintótica, la cota superior asintótica y la cota ajustada… …   Wikipedia Español

  • Ordenamiento de burbuja — La Ordenación de burbuja (Bubble Sort en inglés) es un sencillo algoritmo de ordenamiento. Funciona revisando cada elemento de la lista que va a ser ordenada con el siguiente, intercambiándolos de posición si están en el orden equivocado. Es… …   Wikipedia Español

  • Triangulación de Delaunay — Una triangulación de Delaunay /dəlo ne/, a veces escrito fonéticamente «Deloné», es una red de triángulos que cumple la condición de Delaunay. Esta condición dice que la circunferencia circunscrita de cada triángulo de la red no debe contener… …   Wikipedia Español

Compartir el artículo y extractos

Link directo
… Do a right-click on the link above
and select “Copy Link”