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$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$n en notación asintótica, podrías decir que este algoritmo se ejecuta en un tiempo $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis. ¿Por qué? Porque $n^0 = 1$n, start superscript, 0, end superscript, equals, 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 $\Theta(n^0)$\Theta, left parenthesis, n, start superscript, 0, end superscript, right parenthesis; escribimos $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

Ahora supón que un algoritmo tardó un tiempo $\Theta (\log_{10} n)$\Theta, left parenthesis, log, start base, 10, end base, n, right parenthesis. También podrías decir que tardó un tiempo $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis. 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$a, $b$b y $n$n. Por lo tanto, si $a$a y $b$b son constantes, entonces $\log_a n$log, start base, a, end base, n y $\log_b n$log, start base, b, end base, n difieren solo por un factor de $\log_b a$log, start base, b, end base, 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 $\Theta(\log_a n)$\Theta, left parenthesis, log, start base, a, end base, n, right parenthesis para cualquier constante positiva $a$a. ¿Por qué? El número de intentos es a lo más $\log_2 n + 1$log, start base, 2, end base, n, plus, 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 $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis 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$a y $b$b son constantes y $a < b$a, is less than, b, entonces un tiempo de ejecución de $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis crece más despacio que un tiempo de ejecución de $\Theta(n^b)$\Theta, left parenthesis, n, start superscript, b, end superscript, right parenthesis. Por ejemplo, un tiempo de ejecución de $\Theta(n)$\Theta, left parenthesis, n, right parenthesis, que es $\Theta(n^1)$\Theta, left parenthesis, n, start superscript, 1, end superscript, right parenthesis, crece más despacio que un tiempo de ejecución de $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis. Los exponentes tampoco tienen que ser enteros. Por ejemplo, un tiempo de ejecución de $\Theta(n^2)$\Theta, left parenthesis, n, squared, right parenthesis crece más despacio que un tiempo de ejecución de $\Theta(n^2 \sqrt{n})$\Theta, left parenthesis, n, squared, square root of, n, end square root, right parenthesis, que es $\Theta(n^{2.5})$\Theta, left parenthesis, n, start superscript, 2, point, 5, end superscript, right parenthesis.

La siguiente gráfica comparas el crecimiento de $n$n,$n^2$n, squared y $n^{2.5}$n, start superscript, 2, point, 5, end superscript:

Los logaritmos crecen más despacio que los polinomios. Eso es, $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis crece más despacio que $\Theta(n^a)$\Theta, left parenthesis, n, start superscript, a, end superscript, right parenthesis para cualquier constante positiva $a$a. Pero como el valor de $\log_2 n$log, start base, 2, end base, n crece a medida que $n$n crece, $\Theta(\log_2 n)$\Theta, left parenthesis, log, start base, 2, end base, n, right parenthesis crece más rápido que $\Theta(1)$\Theta, left parenthesis, 1, right parenthesis.

La siguiente gráfica compara el crecimiento de $1$1, $n$n y $\log_2 n$log, start base, 2, end base, 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$a, start superscript, n, end superscript, donde $a > 1$a, is greater than, 1, crece más rápido que cualquier función polinomial $n^b$n, start superscript, b, end superscript, donde $b$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.