Notación asintótica

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 $n$‍, se tarda $6n^2+100n+300$‍ instrucciones de máquina. El término $6n^2$‍ se vuelve más grande que el resto de los términos, $100n+300$‍, una vez que $n$‍ se hace suficientemente grande, 20 en este caso. Aquí hay una gráfica que muestra los valores de $6n^2$‍ y de $100n+300$‍ para valores de $n$‍ de 0 a 100:

Diríamos que el tiempo de ejecución de este algoritmo crece como $n^2$‍, descartando el coeficiente 6 y los términos restantes $100n+300$‍. En realidad no importa qué coeficiente usemos; siempre que el tiempo de ejecución sea $a{n}^2+bn+c$‍, para algunos números $a>0$‍, $b$‍, y $c$‍, siempre habrá un valor de $n$‍ para el cual $a{n}^2$‍ sea mayor que $bn+c$‍, y esta diferencia aumenta a medida que $n$‍ aumenta. Por ejemplo, aquí hay una gráfica que muestra valores de $0.6n^2$‍ y de $1000n+3000$‍, de modo que reducimos el coeficiente de $n^2$‍ por un factor de 10 y aumentamos las otras dos constantes por un factor de 10:

El valor de $n$‍ para el cual $0.6n^2$‍ se hace más grande que $1000n+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 $\mathrm{\Theta }$‍ grande, notación O grande y notación $\mathrm{\Omega }$‍ grande.

Este contenido es una colaboración de los profesores de Dartmouth Computer Science Thomas Cormen y Devin Balkcom junto con el equipo de contenidos de computación de Khan Academy. El contenido está bajo licencia CC-BY-NC-SA.