Funciones en notación asintótica

Cuando usamos notación asintótica para expresar la tasa de crecimiento del tiempo de ejecución de un algoritmo en términos del tamaño de la entrada $n$‍, es bueno tener algunas cosas en mente.

Empecemos con algo sencillo. Supón que el algoritmo se tardó una cantidad constante de tiempo, sin importar el tamaño de su entrada. Por ejemplo, si te dieron un arreglo que ya está ordenado en orden ascendente y tienes que encontrar el elemento mínimo, te tomaría un tiempo constante, ya que el elemento mínimo debe estar en el índice 0. Como queremos usar una función de $n$‍ en notación asintótica, podrías decir que este algoritmo se ejecuta en un tiempo $\mathrm{\Theta }(n^0)$‍. ¿Por qué? Porque $n^0=1$‍ y el tiempo de ejecución del algoritmo está dentro del rango de un factor constante de 1. Sin embargo, en la práctica, no escribimos $\mathrm{\Theta }(n^0)$‍; escribimos $\mathrm{\Theta }(1)$‍.

Ahora supón que un algoritmo tardó un tiempo $\mathrm{\Theta }({\log }_{10}n)$‍. También podrías decir que tardó un tiempo $\mathrm{\Theta }({\log }_{2}n)$‍. Siempre que la base del logaritmo sea una constante, no importa qué base usemos en la notación asintótica. ¿Por qué no? Porque hay una fórmula matemática que dice:

para todos los números positivos $a$‍, $b$‍ y $n$‍. Por lo tanto, si $a$‍ y $b$‍ son constantes, entonces ${\log }_{a}n$‍ y ${\log }_{b}n$‍ difieren solo por un factor de ${\log }_{b}a$‍ y ese es un factor constante que podemos ignorar en la notación asintótica.

Por lo tanto, podemos decir que el peor tiempo de ejecución de la búsqueda binaria es $\mathrm{\Theta }({\log }_{a}n)$‍ para cualquier constante positiva $a$‍. ¿Por qué? El número de intentos es a lo más ${\log }_{2}n+1$‍, generar y probar cada intento tarda un tiempo constante y configurar y regresar tarda un tiempo constante. Sin embargo, como cuestión de práctica, a menudo escribimos que esa búsqueda binaria tarda $\mathrm{\Theta }({\log }_{2}n)$‍ porque en ciencias de la computación nos gusta pensar en potencias de 2.

Hay un orden en las funciones que a menudo vemos cuando analizamos algoritmos usando notación asintótica. Si $a$‍ y $b$‍ son constantes y $a<b$‍, entonces un tiempo de ejecución de $\mathrm{\Theta }(n^a)$‍ crece más despacio que un tiempo de ejecución de $\mathrm{\Theta }(n^b)$‍. Por ejemplo, un tiempo de ejecución de $\mathrm{\Theta }(n)$‍, que es $\mathrm{\Theta }(n^1)$‍, crece más despacio que un tiempo de ejecución de $\mathrm{\Theta }(n^2)$‍. Los exponentes tampoco tienen que ser enteros. Por ejemplo, un tiempo de ejecución de $\mathrm{\Theta }(n^2)$‍ crece más despacio que un tiempo de ejecución de $\mathrm{\Theta }(n^2\sqrt{n})$‍, que es $\mathrm{\Theta }(n^{2.5})$‍.

La siguiente gráfica comparas el crecimiento de $n$‍,$n^2$‍ y $n^{2.5}$‍:

Los logaritmos crecen más despacio que los polinomios. Eso es, $\mathrm{\Theta }({\log }_{2}n)$‍ crece más despacio que $\mathrm{\Theta }(n^a)$‍ para cualquier constante positiva $a$‍. Pero como el valor de ${\log }_{2}n$‍ crece a medida que $n$‍ crece, $\mathrm{\Theta }({\log }_{2}n)$‍ crece más rápido que $\mathrm{\Theta }(1)$‍.

La siguiente gráfica compara el crecimiento de $1$‍, $n$‍ y ${\log }_{2}n$‍:

Aquí hay una lista de funciones en notación asintótica que a menudo encontramos cuando analizamos algoritmos, ordenadas de la que crece más despacio a la que crece más rápido:

Observa que la función exponencial $a^n$‍, donde $a>1$‍, crece más rápido que cualquier función polinomial $n^b$‍, donde $b$‍ es cualquier constante.

La lista anterior no es exhaustiva, hay muchas funciones más con tiempos de ejecución que no están listadas aquí. Con suerte te las encontrarás en tu viaje por las ciencias de la computación.

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.