Contenido principal
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 Cada vez que el bucle for itera, tiene que hacer varias cosas:
- comparar
guessconarray.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
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 Como ya lo argumentamos, el factor constante
Cuando decimos que un tiempo de ejecución particular es de
Para valores pequeños de
No estamos restringidos a solo
Una vez que
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
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
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?
La traducción esta muy incompleta, tanto que leo y no logro comprender la idea, pues faltan valores y nombres de variables.(3 votos)
A mí no me pasa. A lo mejor no es la traducción.(0 votos)
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)
¿Necesito terminar algún curso de algo (ej: Introducción a JS ) para lograr entender esto? O es acaso que ¿esta bien que batalle para entenderlo? me enseñaran algoritmo en segundo semestre del bachillerato y quiero ir preparado... entre el próximo lunes.(2 votos)
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)
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)