Contenido principal
Ciencias de la computación
Curso: Ciencias de la computación > Unidad 1
Lección 3: Notación asintóticaNotación θ grande (Big-θ)
Veamos una implementación sencilla de una búsqueda lineal:
var doLinearSearch = function(array, targetValue) {
for (var guess = 0; guess < array.length; guess++) {
if (array[guess] === targetValue) {
return guess; // ¡lo encontraste!
}
}
return -1; // no lo encontraste
};
Vamos a denotar el tamaño del arreglo (
array.length
) por n. El número máximo de veces que se puede ejecutar el bucle for es n, y este caso peor ocurre cuando el valor que se está buscando no está presente en el arreglo. Cada vez que el bucle for itera, tiene que hacer varias cosas:
- comparar
guess
conarray.length
- compara
array[guess]
contargetValue
- posiblemente regresar el valor de
guess
- incrementar
guess
.
Cada uno de estos pequeños cálculos toma una cantidad constante de tiempo cada vez que se ejecuta. Si el bucle for iterara n veces, entonces el tiempo para todas las n iteraciones es c, start subscript, 1, end subscript, dot, n, donde c, start subscript, 1, end subscript es la suma de los tiempos para los cálculos en una iteración del bucle. Ahora, aquí no podemos decir cuál es el valor de c, start subscript, 1, end subscript, porque depende de la velocidad de la computadora, el lenguaje de programación utilizado, el compilador o intérprete que traduce la fuente del programa fuente en código ejecutable y otros factores.
Este código tiene un poco de encabezado: para crear el bucle for (incluyendo inicializar
guess
a 0) y posiblemente regresar -1
al final. Llamemos al tiempo para este encabezado c, start subscript, 2, end subscript, que también es una constante. Por lo tanto, el tiempo total de la búsqueda lineal en el peor de los casos es de c, start subscript, 1, end subscript, dot, n, plus, c, start subscript, 2, end subscript.Como ya lo argumentamos, el factor constante c, start subscript, 1, end subscript y el término de orden inferior c, start subscript, 2, end subscript no nos dicen nada acerca de la tasa de crecimiento del tiempo de ejecución. Lo que es significativo es que el tiempo de ejecución de una búsqueda lineal en el peor caso crece como el tamaño del arreglo n. La notación que usamos para este tiempo de ejecución es \Theta, left parenthesis, n, right parenthesis. Esa es la letra griega "theta," y decimos "Theta grande de n" o simplemente "Theta de n".
Cuando decimos que un tiempo de ejecución particular es de \Theta, left parenthesis, n, right parenthesis, estamos diciendo que una vez que n sea suficientemente grande, el tiempo de ejecución será por lo menos k, start subscript, 1, end subscript, dot, n y a lo más k, start subscript, 2, end subscript, dot, n para algunas constantes k, start subscript, 1, end subscript y k, start subscript, 2, end subscript. Aquí está cómo pensar acerca de \Theta, left parenthesis, n, right parenthesis:
Para valores pequeños de n, no nos importa cómo se compara el tiempo de ejecución con k, start subscript, 1, end subscript, dot, n o k, start subscript, 2, end subscript, dot, n. Pero una vez que n se hace suficientemente grande, sobre o a la derecha de la línea punteada, el tiempo de ejecución debe estar entre k, start subscript, 1, end subscript, dot, n y k, start subscript, 2, end subscript, dot, n. Mientra existan estas constantes k, start subscript, 1, end subscript y k, start subscript, 2, end subscript, decimos que el tiempo de ejecución es \Theta, left parenthesis, n, right parenthesis.
No estamos restringidos a solo n en la notación Θ grande. Podemos usar cualquier función, como n, squared, n, log, start base, 2, end base, n, o cualquier otra función de n. Aquí está cómo pensar acerca del tiempo de ejecución que es \Theta, left parenthesis, f, left parenthesis, n, right parenthesis, right parenthesis para alguna función f, left parenthesis, n, right parenthesis:
Una vez que n se hace suficientemente grande, el tiempo de ejecución está entre k, start subscript, 1, end subscript, dot, f, left parenthesis, n, right parenthesis y k, start subscript, 2, end subscript, dot, f, left parenthesis, n, right parenthesis.
En la práctica, simplemente descartamos factores constantes y términos de orden inferior. Otra ventaja de usar la notación Θ grande es que no tenemos que preocuparnos por las unidades de tiempo que estamos usando. Por ejemplo, supón que calculas que un tiempo de ejecución es de 6, n, squared, plus, 100, n, plus, 300 microsegundos. O tal vez sean milisegundos. Cuando usas la notación Θ grande, no lo especificas. También descartas el factor 6 y los términos de orden inferior 100, n, plus, 300, y solo dices que el tiempo de ejecución es de \Theta, left parenthesis, n, squared, right parenthesis.
Cuando usamos la notación Θ grande, estamos diciendo que tenemos una cota asintóticamente ajustada sobre el tiempo de ejecución. "Asintóticamente" porque importa solo para valores grandes de n. "Cota ajustada" porque ajustamos el tiempo de ejecución dentro del rango de una constante hacia arriba y hacia abajo.
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?
- Cuando usamos la notación?(2 votos)
- La utilizamos cuando necesitamos saber la estimación del tiempo de ejecución de un algoritmo y compararlo con otros(1 voto)
- por que no tenemos que preocuparnos de las unidades de tiempo cuando usamos notaciones grandes?(2 votos)
- Podemos suprimir las unidades de tiempo porque depende de la velocidad de ejecución del programa el cual depende de diversos factores que se han comentado anteriormente.(2 votos)
- como se puede resolver la complejidad de algun problema en funcion de un algoritmo(2 votos)
- La traducción esta muy incompleta, tanto que leo y no logro comprender la idea, pues faltan valores y nombres de variables.(2 votos)
- A mí no me pasa. A lo mejor no es la traducción.(0 votos)
- para que descartamos factores constantes y términos de orden inferior?(1 voto)
- Porque da igual el algoritmo que uses para solucionar algo, esos pasos siempre van a estar ahí y van a costar siempre lo mismo, lo resuelvas como lo resuelvas, así que para qué ponerlos, digamos que limpias la notación con lo redundante. Lo que se busca es una manera de comparar algoritmos según el tamaño del input/variable de entrada. Es decir, se necesita saber cuanto va a tardar en calcular algo y si este tiempo depende y cómo depende de la cantidad o tamaño de lo que se calcula. Al final hay varias maneras de conseguir una solución, y unas tienen más pasos o tardan más que otras.(1 voto)
- ¿Como Se Sabe Si Es Una ejecucion Grande?(1 voto)
- cuando tenemos una cota asintóticamente ajustada sobre el tiempo de ejecución(1 voto)
- cuales serian las funciones de compliador(1 voto)
- var doLinearSearch = function(array) {
for (var guess = 0; guess < array.length; guess++) {
if (array[guess] === targetValue) {
return guess; // ¡lo encontraste!
}
}
return -1; // no lo encontraste
};(3 votos)
- como se complementa una búsqueda binaria(1 voto)