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:
Una función f(x) pertenece a Ω(g(x)) cuando existe una constante positiva c tal que a partir de un valor , 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 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 con respecto a f(x) cuando x tiende a infinito.
La función x² 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 x²).
La función x²+200x está acotada inferiormente por x². Quiere decir que cuando x tiende a infinito el valor de 200x se puede despreciar con respecto al de x².Además de que nunca va a tocar a cero
Introduction to Algorithms, Second Edition by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein
Datos:Q8351379
Noviembre 03, 2021
cota, inferior, asintótica, análisis, algoritmos, cota, inferior, asintótica, función, sirve, cota, inferior, otra, función, cuando, argumento, tiende, infinito, usualmente, utiliza, notación, para, referirse, funciones, acotadas, inferiormente, función, más, . En analisis de algoritmos una cota inferior asintotica es una funcion que sirve de cota inferior de otra funcion cuando el argumento tiende a infinito Usualmente se utiliza la notacion W g x para referirse a las funciones acotadas inferiormente por la funcion g x Mas formalmente se define W g x f x existen c x 0 constantes positivas tales que x x 0 x 0 c g x f x displaystyle Omega g x left begin matrix f x mbox existen c x 0 mbox constantes positivas tales que forall x x 0 leq x 0 leq cg x leq f x end matrix right Una funcion f x pertenece a W g x cuando existe una constante positiva c tal que a partir de un valor x 0 displaystyle x 0 c g x displaystyle cg x no supera f x Quiere decir que la funcion f es superior a g a partir de un valor dado salvo por un factor constante La cota inferior asintotica tiene utilidad en Teoria de la complejidad computacional a la hora de calcular la complejidad del mejor caso para los algoritmos f x W g x A pesar de que W g x esta definido como un conjunto se acostumbra escribir f x W g x en lugar de f x W g x Muchas veces tambien se habla de una funcion nombrando unicamente su expresion como en x en lugar de h x x siempre que este claro cual es el parametro de la funcion dentro de la expresion En la grafica se da un ejemplo esquematico de como se comporta c g x displaystyle cg x con respecto a f x cuando x tiende a infinito La cota ajustada asintotica notacion 8 tiene relacion con las cotas superior notacion O e inferior asintoticas f x 8 g x si y solo si f x O g x y f x W g x displaystyle f x Theta g x mbox si y solo si f x O g x mbox y f x Omega g x Ejemplos EditarLa funcion x puede ser acotada inferiormente por la funcion x Para demostrarlo basta notar que para todo valor de x 1 se cumple x x Por tanto x W x sin embargo x no sirve como cota superior para x La funcion x 200x esta acotada inferiormente por x Quiere decir que cuando x tiende a infinito el valor de 200x se puede despreciar con respecto al de x Ademas de que nunca va a tocar a ceroVease tambien EditarCota ajustada asintotica Cota superior asintotica Notacion de LandauBibliografia EditarIntroduction to Algorithms Second Edition by Thomas H Cormen Charles E Leiserson Ronald L Rivest Clifford Stein Datos Q8351379 Obtenido de https es wikipedia org w index php title Cota inferior asintotica amp oldid 117829392, wikipedia, wiki, leyendo, leer, libro, biblioteca,
