Cota ajustada asintótica

Cota ajustada asintótica

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 Θ(g(x)) para referirse a las funciones acotadas por la función g(x).

Más formalmente se define:

\Theta(g(x)) = \left\{\begin{matrix} f(x) : \mbox{existen } c_1,c_2,x_0 \mbox{ constantes positivas tales que} \\ \forall x:x_0\le x: 0\le c_1g(x)\le f(x)\le c_2g(x) \end{matrix}\right\}

Una función f(x) pertenece a Θ(g(x)) cuando existen constantes positivas c1 y c2 tales que a partir de un valor x0 f(x) se encuentra atrapada entre c1g(x) y c2g(x). Quiere decir que las funciones f y g son iguales a partir de un valor dado salvo por una factor constante. Por tanto tiene sentido tomar a g como un representante de f.

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 la función 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 cómo se comportan c1g(x) y c2g(x) con respecto a f(x) cuando x tiende a infinito.

La cota ajustada asintótica tiene relación con las cotas superior e inferior asintóticas (respectivamente las notaciones O y Ω):

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

Ejemplos

  • La función f(x) = x+10 puede ser acotada por la función g(x) = x. Para demostrarlo basta notar que para todo valor de x≥1 se cumple que g(x)≤f(x)≤11g(x), es decir x ≤ x+10 ≤ 11x . Por lo tanto x+10 = Θ(x).

Véase también

Bibliografía

  • Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Obtenido de "Cota ajustada asint%C3%B3tica"

Wikimedia foundation. 2010.

Игры ⚽ Поможем написать реферат

Mira otros diccionarios:

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

  • 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

  • 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

  • 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

  • Ordenamiento por selección — Animación del Selection Sort El ordenamiento por selección (Selection Sort en inglés) es un algoritmo de ordenamiento que requiere O(n2) operaciones para ordenar una lista de n elementos. Su funcionamiento es el siguiente: Buscar el mínimo… …   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

  • Technicolor (física) — Las teorías Technicolor son modelos de física Más allá del modelo estándar que nos llevan a la ruptura de la simetría electrodébil, el mecanismo por el cual las partículas elementales adquieren masa. Las primeras teorías technicolor se basaron en …   Wikipedia Español

Compartir el artículo y extractos

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