Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 3: Notación asintóticaNotación Omega grande (Big-Ω)
A veces, queremos decir que un algoritmo toma por lo menos una cierta cantidad de tiempo, sin dar una cota superior. Utilizamos la notación Ω grande; esa es la letra griega "omega".
Si un tiempo de ejecución es \Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, entonces para una n suficientemente grande, el tiempo de ejecución es por lo menos k, dot, f, left parenthesis, n, right parenthesis para alguna constante k. Aquí está cómo pensar acerca de un tiempo de ejecución que es \Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis:
Decimos que el tiempo de ejecución es "Ω grande de f, left parenthesis, n, right parenthesis". Usamos la notación Ω grande para límites asintóticos inferiores, ya que acota el crecimiento del tiempo de ejecución por abajo para entradas de tamaños suficientemente grandes.
Así como \Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis automáticamente implica O, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis, también automáticamente implica \Omega, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis. Así que podemos decir que el tiempo de ejecución del peor caso de la búsqueda binaria es \Omega, left parenthesis, log, start base, 2, end base, n, right parenthesis.
También podemos hacer afirmaciones correctas, pero imprecisas, al usar la notación Ω grande. Por ejemplo, si en verdad tienes un millón de pesos en el bolsillo, ciertamente podrías decir "tengo una cantidad de dinero en mi bolsillo y es por lo menos de 10 pesos". Eso es correcto, pero ciertamente no muy preciso. Del mismo modo, podemos decir de manera correcta pero imprecisa que el tiempo de ejecución del peor caso de la búsqueda binaria es \Omega, left parenthesis, 1, right parenthesis, porque sabemos que tarda por lo menos un tiempo constante.
Por supuesto, típicamente, cuando hablamos acerca de los algoritmos, tratamos de describir sus tiempos de ejecución lo más precisos posibles. Aquí proporcionamos ejemplos de afirmaciones imprecisas para ayudarte a entender mejor \Omega grande, O grande y \Theta grande.
Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom, con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.
¿Quieres unirte a la conversación?
- En "De modo que podemos decir que el peor tiempo de ejecución de la búsqueda binaria es Ω(lgn)" y "el peor tiempo de ejecución de la búsqueda binaria es Ω(1)"
no sería el MEJOR tiempo de ejecución posible? al acotar por abajo no sería "en el mejor caso posible tardará Ω(1), por lo tanto, en un caso peor podrá tardar más"(8 votos)- Parece que deberíamos decir "MEJOR" porque es muy bueno, pero precisamente por ello decimos que es lo peor que nos podría pasar. Piensenlo como: "Lo peor que me podría pasar si leo un libro sería aprender un par de palabras nuevas" = (AL MENOS APRENDERÉ ALGO). Espero haberlo aclarado un poco.(4 votos)
- En "De modo que podemos decir que el peor tiempo de ejecución de la búsqueda binaria es Ω(lgn)" y "el peor tiempo de ejecución de la búsqueda binaria es Ω(1)"
no sería mas rentable tiempo de ejecución posible?(2 votos) - ¿Para que Usamos La Notacion Grande?(1 voto)
- que son límites asintóticos inferiores(1 voto)
- Teniendo en cuenta el valor de la Ω grande se puede interpretar el punto de equilibrio en el plano?(1 voto)
- pues el adgritmo see dmra ssegun el contenio que tanga o presenta(1 voto)
- para qué sirve tener una función Theta que describe las dos cotas, una O que define solo la cota superior y una omega que define la cota inferior?
En qué casos debo usar cada una?(1 voto)