Notación Asintótica
Dos algoritmos requieren 3 log(20 + ) y log (20000 + 3) minutos respectivamente, para resolver casos de tamaño n . Realice una demostración formal para determinar cuál es el tamaño del caso más pequeño en el cual el segundo algoritmo es más rápido que el primero.
Respuestas
Respuesta:
Explicación: Hasta ahora, hemos analizado la búsqueda lineal y la búsqueda binaria al contar el número máximo de intentos que necesitamos hacer. Pero lo que en realidad queremos saber es cuánto tiempo tardan estos algoritmos. Estamos interesados en el tiempo, no solo en los intentos. Los tiempos de ejecución de la búsqueda lineal y la búsqueda binaria incluyen el tiempo necesario para hacer y revisar los intentos, pero hay más acerca de estos algoritmos.
El tiempo de ejecución de un algoritmo depende de cuánto tiempo le tome a una computadora ejecutar las líneas de código del algoritmo, y eso depende de la velocidad de la computadora, el lenguaje de programación y el compilador que traduce el programa del lenguaje de programación al código que se ejecuta directamente en la computadora, entre otros factores.
Pensemos más cuidadosamente acerca del tiempo de ejecución de un algoritmo. Podemos usar una combinación de dos ideas. Primero, necesitamos determinar cuánto tiempo se tarda el algoritmo, en términos del tamaño de su entrada. Esta idea tiene sentido intuitivamente, ¿o no? Ya vimos que el número máximo de intentos en una búsqueda lineal y una búsqueda binaria aumenta a medida que la longitud del arreglo aumenta. O piensa en un GPS. Si solo supiera acerca del sistema carretero del país, y no acerca de cada pequeño camino, sería capaz de encontrar rutas más rápido, ¿cierto? Así que pensamos acerca del tiempo de ejecución del algoritmo como una función del tamaño de su entrada.
La segunda idea es que debemos enfocarnos en qué tan rápido crece una función con el tamaño de la entrada. A esto lo llamamos la tasa de crecimiento del tiempo de ejecución. Para mantener las cosas manejables, tenemos que simplificar la función para extraer la parte más importante y dejar de lado las partes menos importantes. Por ejemplo, supón que un algoritmo, que corre con un entrada de tamaño nnn, se tarda 6n^2 + 100n + 3006n
2
+100n+3006, n, squared, plus, 100, n, plus, 300 instrucciones de máquina. El término 6n^26n
2
6, n, squared se vuelve más grande que el resto de los términos, 100 n + 300100n+300100, n, plus, 300, una vez que nnn se hace suficientemente grande, 20 en este caso. Aquí hay una gráfica que muestra los valores de 6n^26n
2
6, n, squared y de 100n + 300100n+300100, n, plus, 300 para valores de nnn de 0 a 100:
Diríamos que el tiempo de ejecución de este algoritmo crece como n^2n
2
n, squared, descartando el coeficiente 6 y los términos restantes 100n + 300100n+300100, n, plus, 300. En realidad no importa qué coeficiente usemos; siempre que el tiempo de ejecución sea an^2 + bn + can
2
+bn+ca, n, squared, plus, b, n, plus, c, para algunos números a > 0a>0a, is greater than, 0, bbb, y ccc, siempre habrá un valor de nnn para el cual an^2an
2
a, n, squared sea mayor que bn + cbn+cb, n, plus, c, y esta diferencia aumenta a medida que nnn aumenta. Por ejemplo, aquí hay una gráfica que muestra valores de 0.6n^20.6n
2
0, point, 6, n, squared y de 1000n + 30001000n+30001000, n, plus, 3000, de modo que reducimos el coeficiente de n^2n
2
n, squared por un factor de 10 y aumentamos las otras dos constantes por un factor de 10:
El valor de nnn para el cual 0.6n^20.6n
2
0, point, 6, n, squared se hace más grande que 1000n + 30001000n+30001000, n, plus, 3000 aumentó, pero siempre habrá tal valor, sin importar las constantes.
Al descartar los términos menos significativos y los coeficientes constantes, podemos enfocarnos en la parte importante del tiempo de ejecución de un algoritmo (su tasa de crecimiento) sin involucrarnos en detalles que complican nuestro entendimiento. Cuando descartamos los coeficientes constantes y los términos menos significativos, usamos notación asintótica. Veremos tres formas: notación \ThetaΘ\Theta grande, notación O grande y notación \OmegaΩ\Omega grande.