Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 3: Notación asintóticaNotación O grande (Big-O)
Usamos la notación Θ grande para acotar de manera asintótica el crecimiento de un tiempo de ejecución a que esté dentro de factores constantes por arriba y por abajo. A veces queremos acotar solo por arriba.
Por ejemplo, aunque el peor tiempo de ejecución de la búsqueda binaria es , sería incorrecto decir que búsqueda binaria se ejecuta en un tiempo en todos los casos. ¿Qué pasa si encontramos el valor objetivo después del primer intento? Entonces se ejecuta en un tiempo . El tiempo de ejecución de la búsqueda binaria nunca es peor que , pero a veces es mejor.
Sería conveniente tener una forma de notación asintótica que signifique "el tiempo de ejecución crece a lo más por este tanto, pero puede crecer más lentamente". Usamos la notación "O grande" justo para estas ocasiones.
Si un tiempo de ejecución es , entonces para suficientemente grande, el tiempo de ejecución es a lo más para alguna constante . Aquí está cómo pensar acerca de un tiempo de ejecución que es :
Decimos que el tiempo de ejecución es "O grande de " o simplemente "O de ". Usamos la notación O grande para cotas superiores asintóticas, ya que acota el crecimiento del tiempo de ejecución por arriba para entradas suficientemente grandes.
Ahora tenemos una manera de caracterizar el tiempo de ejecución de la búsqueda binaria en todos los casos. Podemos decir que el tiempo de ejecución de una búsqueda binaria siempre es . Podemos hacer una afirmación más fuerte acerca del peor caso del tiempo de ejecución: es . Pero para una afirmación que cubra todos los casos, la afirmación más fuerte que podemos hacer es que la búsqueda binaria se ejecuta en un tiempo .
Si regresamos a la definición de la notación de Θ grande, te darás cuenta de que se parece mucho a la notación O grande, excepto que la notación Θ grande acota el tiempo de ejecución tanto por arriba como por abajo, en lugar de solo por arriba. Si decimos que un tiempo de ejecución es en una situación particular, entonces también es . Por ejemplo, podemos decir que como el tiempo de ejecución del peor caso de una búsqueda binaria es , también es .
Lo inverso no es necesariamente cierto: como hemos visto, podemos decir que la búsqueda binaria siempre se ejecuta en un tiempo pero no siempre se ejecuta en un tiempo .
Como la notación O grande solo da una cota asintótica superior, y no una cota superior asintóticamente ajustada, podemos hacer afirmaciones que a primera vista parecen incorrectas, pero que son técnicamente correctas. Por ejemplo, es absolutamente correcto decir que la búsqueda binaria se ejecuta en un tiempo . Eso es porque el tiempo de ejecución crece no más rápido que una constante multiplicada por . De hecho, crece más lento.
Piénsalo de esta manera. Supón que tienes 10 pesos en el bolsillo. Vas con tu amigo y le dices: "tengo una cantidad de dinero en mi bolsillo, y te garantizo que no es más de 1 millón de pesos". Tu afirmación es totalmente cierta, aunque no muy precisa.
1 millón de pesos es una cota superior de los 10 pesos, así como es una cota superior del tiempo de ejecución de la búsqueda binaria. Otras cotas superiores, imprecisas, de una búsqueda binaria serían , y . Pero, en cualquier caso, ninguna de , , ni serían correctas para describir el tiempo de ejecución de la búsqueda binaria.
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?
- esta muy bueno el tema, lo entendi(4 votos)
- ¿para que sirve la notación o grande ?(4 votos)
- En realidad es una de las notaciones asintóticas más usadas, lo que nos dice es cuanto demoraría el algoritmo en 'el peor de los casos', una condición muy útil cuando tu función debe procesar una gran cantidad de datos o te interesa analizar el algoritmo con una entrada n cualquiera, por ejemplo, en la busqueda binaria, dándose las peores condiciones (el máximo número de divisiones posibles) y un gran número de datos (n), ya sabes que lo máximo que demora tu programa es O (lg n) y a partir de esa información determinar si un algoritmo es eficiente con una entrada n arbitraria, en el caso de la búsqueda binaria, lo es.(14 votos)
- ¿Por Que La Busqueda Binaria Se Ejecuta En Un Tiempo?(3 votos)
- Porque todo proceso tiene un tiempo de ejecución.(4 votos)
- ¿que es una cota asintóticamente ajustada y para que sirve?(3 votos)
- Para Que Se Utiliza La Notacion Grande?(3 votos)
- que son cotas superiores asintóticas(2 votos)
- que es una anotación asintatica ?(1 voto)
- gracias por el aprendizaje(1 voto)
- Θ(n), \Theta(n^2) Θ(n
2
), \Theta(n^3) Θ(n
3
) ni \Theta(2^n) Θ(2
n
) que significado tiene(1 voto)