Cota inferior asintótica

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 inferiormente por la función g(x).

Más formalmente se define:

\Omega(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existen } c,x_0 \mbox{ constantes positivas tales que} \\ \forall x:x_0\le x: 0\le cg(x)\le f(x) \end{matrix}\right\}

Una función f(x) pertenece a Ω(g(x)) cuando existe una constante positiva c tal que a partir de un valor x0, cg(x) no supera f(x). Quiere decir que la función f es superior a g a partir de un valor dado salvo por un factor constante.

La cota inferior asintótica tiene utilidad en Teoría de la complejidad computacional a la hora de calcular la complejidad del mejor caso para los algoritmos.

f(x)=Ω(g(x)).

A pesar de que Ω(g(x)) está definido como un conjunto, se acostumbra escribir f(x)=Ω(g(x)) en lugar de f(x) ∈ Ω(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 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 superior (notación O) e inferior asintóticas :

f(x) = Θ(g(x)) si y solo si f(x) = O(g(x)) y f(x) = Ω(g(x))

Ejemplos

  • La función puede ser acotada inferiormente por la función x. Para demostrarlo basta notar que para todo valor de x≥1 se cumple x≤x². Por tanto x² = Ω(x) (sin embargo, x no sirve como cota superior para ).
  • La función x²+200x está acotada inferiormente por . Quiere decir que cuando x tiende a infinito el valor de 200x se puede despreciar con respecto al de .

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 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 — 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 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… …   Wikipedia Español

  • 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 — 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

  • 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

  • Algoritmo — Los diagramas de flujo sirven para representar algoritmos de manera gráfica. En matemáticas, ciencias de la computación y disciplinas relacionadas, un algoritmo (del griego y latín, dixit algorithmus y éste a su vez del matemático persa Al… …   Wikipedia Español

  • Función linearítmica — En ciencias de la computación una función linearítmica, es aquella de la forma n · log n. Es decir el producto entre una función lineal y una logaritmica.[1] En terminos de complejidad algorítmica, la función linearítmica crece más rápido que la… …   Wikipedia Español

  • Serie de los inversos de los números primos — En el siglo III a. C., Euclides demostró la existencia de infinitos números primos. En el siglo XVIII, Leonhard Euler demostró un resultado aún más profundo: La suma de los recíprocos de todos los números primos diverge. Leonhard Euler… …   Wikipedia Español

Compartir el artículo y extractos

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