En informática , el análisis de algoritmos es el proceso de encontrar la complejidad computacional de los algoritmos : la cantidad de tiempo, almacenamiento u otros recursos necesarios para ejecutarlos. Por lo general, esto implica determinar una función que relaciona el tamaño de la entrada de un algoritmo con la cantidad de pasos que toma (su complejidad temporal ) o la cantidad de ubicaciones de almacenamiento que utiliza (su complejidad espacial ). Se dice que un algoritmo es eficiente cuando los valores de esta función son pequeños o crecen lentamente en comparación con el crecimiento del tamaño de la entrada. Diferentes entradas del mismo tamaño pueden hacer que el algoritmo tenga un comportamiento diferente, por lo que las descripciones de los casos mejor, peor y promedio podrían ser de interés práctico. Cuando no se especifica lo contrario, la función que describe el rendimiento de un algoritmo suele ser un límite superior , determinado a partir de las entradas del peor caso al algoritmo.
El término "análisis de algoritmos" fue acuñado por Donald Knuth . [1] El análisis de algoritmos es una parte importante de una teoría de la complejidad computacional más amplia , que proporciona estimaciones teóricas de los recursos necesarios para cualquier algoritmo que resuelva un problema computacional determinado . Estas estimaciones proporcionan una idea de direcciones razonables de búsqueda de algoritmos eficientes .
En el análisis teórico de algoritmos es común estimar su complejidad en sentido asintótico, es decir, estimar la función de complejidad para entradas arbitrariamente grandes. Para este fin se utilizan la notación Big O , la notación Big-omega y la notación Big-theta . [2] Por ejemplo, se dice que la búsqueda binaria se ejecuta en un número de pasos proporcional al logaritmo del tamaño n de la lista ordenada que se busca, o en O (log n ) , coloquialmente "en tiempo logarítmico ". Por lo general, se utilizan estimaciones asintóticas porque diferentes implementaciones del mismo algoritmo pueden diferir en eficiencia. Sin embargo, las eficiencias de dos implementaciones "razonables" de un algoritmo determinado están relacionadas por un factor multiplicativo constante llamado constante oculta .
A veces se pueden calcular medidas exactas (no asintóticas) de eficiencia, pero normalmente requieren ciertas suposiciones relativas a la implementación particular del algoritmo, llamado modelo de cálculo . Un modelo de computación puede definirse en términos de una computadora abstracta , por ejemplo, la máquina de Turing , y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si la lista ordenada a la que aplicamos la búsqueda binaria tiene n elementos y podemos garantizar que cada búsqueda de un elemento en la lista se puede realizar en una unidad de tiempo, entonces como máximo log 2 ( n ) + 1 unidades de tiempo son necesario para devolver una respuesta.
Las estimaciones de eficiencia del tiempo dependen de lo que definimos como un paso. Para que el análisis se corresponda de manera útil con el tiempo de ejecución real, se debe garantizar que el tiempo requerido para realizar un paso esté limitado por una constante. Hay que tener cuidado aquí; por ejemplo, algunos análisis cuentan la suma de dos números como un paso. Esta suposición puede no estar justificada en ciertos contextos. Por ejemplo, si los números involucrados en un cálculo pueden ser arbitrariamente grandes, ya no se puede suponer que el tiempo requerido para una sola suma sea constante.
Generalmente se utilizan dos modelos de costos: [3] [4] [5] [6] [7]
Este último es más complicado de utilizar, por lo que sólo se emplea cuando es necesario, por ejemplo en el análisis de algoritmos aritméticos de precisión arbitraria , como los utilizados en criptografía .
Un punto clave que a menudo se pasa por alto es que los límites inferiores publicados para los problemas a menudo se dan para un modelo de cálculo que es más restringido que el conjunto de operaciones que se podrían usar en la práctica y, por lo tanto, hay algoritmos que son más rápidos de lo que ingenuamente sería. creía posible. [8]
El análisis del tiempo de ejecución es una clasificación teórica que estima y anticipa el aumento en el tiempo de ejecución (o tiempo de ejecución) de un algoritmo a medida que aumenta su tamaño de entrada (generalmente denotado como n ). La eficiencia en tiempo de ejecución es un tema de gran interés en informática : un programa puede tardar segundos, horas o incluso años en terminar de ejecutarse, dependiendo del algoritmo que implemente. Si bien las técnicas de creación de perfiles de software se pueden utilizar para medir el tiempo de ejecución de un algoritmo en la práctica, no pueden proporcionar datos de tiempo para todas las infinitas entradas posibles; esto último sólo puede lograrse mediante los métodos teóricos de análisis en tiempo de ejecución.
Dado que los algoritmos son independientes de la plataforma (es decir, un algoritmo determinado puede implementarse en un lenguaje de programación arbitrario en una computadora arbitraria que ejecuta un sistema operativo arbitrario ), existen inconvenientes importantes adicionales al uso de un enfoque empírico para medir el rendimiento comparativo de un conjunto determinado de algoritmos.
Tomemos como ejemplo un programa que busca una entrada específica en una lista ordenada de tamaño n . Supongamos que este programa se implementara en la Computadora A, una máquina de última generación, que utiliza un algoritmo de búsqueda lineal , y en la Computadora B, una máquina mucho más lenta, que utiliza un algoritmo de búsqueda binaria . Las pruebas comparativas en las dos computadoras que ejecutan sus respectivos programas podrían verse así:
Con base en estas métricas, sería fácil llegar a la conclusión de que la Computadora A está ejecutando un algoritmo que es muy superior en eficiencia al de la Computadora B. Sin embargo, si el tamaño de la lista de entrada se aumenta a un número suficiente, se demuestra dramáticamente que esa conclusión es errónea:
La computadora A, que ejecuta el programa de búsqueda lineal, muestra una tasa de crecimiento lineal . El tiempo de ejecución del programa es directamente proporcional a su tamaño de entrada. Duplicar el tamaño de entrada duplica el tiempo de ejecución, cuadriplicar el tamaño de entrada cuadriplica el tiempo de ejecución, y así sucesivamente. Por otro lado, la computadora B, que ejecuta el programa de búsqueda binaria, muestra una tasa de crecimiento logarítmica . Cuadriplicar el tamaño de entrada solo aumenta el tiempo de ejecución en una cantidad constante (en este ejemplo, 50.000 ns). Aunque la Computadora A es aparentemente una máquina más rápida, la Computadora B inevitablemente superará a la Computadora A en tiempo de ejecución porque ejecuta un algoritmo con una tasa de crecimiento mucho más lenta.
Informalmente, se puede decir que un algoritmo exhibe una tasa de crecimiento del orden de una función matemática si más allá de un cierto tamaño de entrada n , la función f ( n ) multiplicada por una constante positiva proporciona un límite superior para el tiempo de ejecución de esa función. algoritmo. En otras palabras, para un tamaño de entrada dado n mayor que algún n 0 y una c constante , el tiempo de ejecución de ese algoritmo nunca será mayor que c × f ( n ) . Este concepto se expresa frecuentemente utilizando la notación O grande. Por ejemplo, dado que el tiempo de ejecución de la ordenación por inserción crece cuadráticamente a medida que aumenta su tamaño de entrada, se puede decir que la ordenación por inserción es de orden O ( n 2 ) .
La notación O grande es una forma conveniente de expresar el peor de los casos para un algoritmo determinado, aunque también se puede usar para expresar el caso promedio; por ejemplo, el peor de los casos para la clasificación rápida es O ( n 2 ) , pero el tiempo de ejecución promedio del caso es O ( n log n ) .
Suponiendo que el tiempo de ejecución sigue la regla de potencia, t ≈ kn a , el coeficiente a se puede encontrar [9] tomando medidas empíricas del tiempo de ejecución { t 1 , t 2 } en algunos puntos del tamaño del problema { n 1 , n 2 }, y calculando t 2 / t 1 = ( n 2 / n 1 ) a de manera que a = log( t 2 / t 1 )/log( n 2 / n 1 ) . En otras palabras, esto mide la pendiente de la línea empírica en la gráfica log-log del tiempo de ejecución versus el tamaño de entrada, en algún punto de tamaño. Si el orden de crecimiento de hecho sigue la regla de la potencia (y por lo tanto la línea en la gráfica log-log es de hecho una línea recta), el valor empírico depermanecerá constante en diferentes rangos, y si no, cambiará (y la línea es una línea curva), pero aún así podría servir para comparar dos algoritmos dados cualesquiera en cuanto a sus órdenes empíricos locales de comportamiento de crecimiento. Aplicado a la tabla anterior:
Se ve claramente que el primer algoritmo exhibe un orden lineal de crecimiento que de hecho sigue la regla de potencia. Los valores empíricos del segundo están disminuyendo rápidamente, lo que sugiere que sigue otra regla de crecimiento y, en cualquier caso, tiene órdenes de crecimiento locales mucho más bajos (y mejora aún más), empíricamente, que el primero.
La complejidad del tiempo de ejecución para el peor de los casos de un algoritmo determinado a veces se puede evaluar examinando la estructura del algoritmo y haciendo algunas suposiciones simplificadoras. Considere el siguiente pseudocódigo :
1 obtengo un entero positivo n de la entrada 2 si n > 103 imprime "Esto puede tardar un poco..."4 para i = 1 an5 para j = 1 a i6 imprimir i * j7 imprime "¡Listo!"
Una computadora determinada tardará una cantidad de tiempo discreta en ejecutar cada una de las instrucciones involucradas en la ejecución de este algoritmo. Digamos que se considera que las acciones realizadas en el paso 1 consumen tiempo como máximo T 1 , el paso 2 utiliza tiempo como máximo T 2 , y así sucesivamente.
En el algoritmo anterior, los pasos 1, 2 y 7 sólo se ejecutarán una vez. Para una evaluación del peor de los casos, se debe suponer que también se ejecutará el paso 3. Por lo tanto, la cantidad total de tiempo para ejecutar los pasos 1 a 3 y el paso 7 es:
Los bucles de los pasos 4, 5 y 6 son más complicados de evaluar. La prueba de bucle externo en el paso 4 se ejecutará ( n + 1) veces, [10], lo que consumirá T 4 ( n + 1) tiempo. El bucle interno, por otro lado, se rige por el valor de j, que se repite de 1 a i . En la primera pasada por el bucle externo, j itera de 1 a 1: el bucle interno realiza una pasada, por lo que ejecutar el cuerpo del bucle interno (paso 6) consume T 6 tiempo, y la prueba del bucle interno (paso 5) consume 2 T 5 veces. Durante el siguiente paso por el bucle exterior, j itera de 1 a 2: el bucle interior realiza dos pasadas, por lo que ejecutar el cuerpo del bucle interior (paso 6) consume 2 T 6 de tiempo, y la prueba del bucle interior (paso 5) consume 3 T 5 veces.
En total, el tiempo total necesario para ejecutar el cuerpo del bucle interno se puede expresar como una progresión aritmética :
que se puede factorizar [11] como
El tiempo total necesario para ejecutar la prueba del bucle interno se puede evaluar de manera similar:
que se puede factorizar como
Por tanto, el tiempo total de ejecución de este algoritmo es:
lo que se reduce a
Como regla general , se puede suponer que el término de orden más alto en cualquier función dada domina su tasa de crecimiento y, por lo tanto, define su orden en el tiempo de ejecución. En este ejemplo, n 2 es el término de orden más alto, por lo que se puede concluir que f ( n ) = O ( n 2 ) . Formalmente esto se puede demostrar de la siguiente manera:
demostrar que
Sea k una constante mayor o igual a [ T 1 .. T 7 ] Por lo tanto
Un enfoque más elegante para analizar este algoritmo sería declarar que [ T 1 .. T 7 ] son todos iguales a una unidad de tiempo, en un sistema de unidades elegidas de modo que una unidad sea mayor o igual a los tiempos reales para estos pasos. Esto significaría que el tiempo de ejecución del algoritmo se desglosa de la siguiente manera: [12]
La metodología de análisis en tiempo de ejecución también se puede utilizar para predecir otras tasas de crecimiento, como el consumo de espacio de memoria . Como ejemplo, considere el siguiente pseudocódigo que administra y reasigna el uso de memoria por parte de un programa según el tamaño del archivo que administra ese programa:
mientras el archivo aún está abierto: sea n = tamaño del archivo por cada 100.000 kilobytes de aumento en el tamaño del archivo , duplique la cantidad de memoria reservada
En este caso, a medida que aumenta el tamaño del archivo n, la memoria se consumirá a una tasa de crecimiento exponencial , que es de orden O (2 n ) . Se trata de una tasa de crecimiento extremadamente rápida y probablemente inmanejable del consumo de recursos de memoria .
El análisis de algoritmos es importante en la práctica porque el uso accidental o involuntario de un algoritmo ineficiente puede afectar significativamente el rendimiento del sistema. En aplicaciones urgentes, un algoritmo que tarda demasiado en ejecutarse puede hacer que sus resultados queden obsoletos o inútiles. Un algoritmo ineficiente también puede terminar requiriendo una cantidad antieconómica de potencia informática o almacenamiento para funcionar, lo que nuevamente lo vuelve prácticamente inútil.
El análisis de algoritmos normalmente se centra en el rendimiento asintótico, particularmente en el nivel elemental, pero en aplicaciones prácticas los factores constantes son importantes y, en la práctica, los datos del mundo real siempre tienen un tamaño limitado. El límite suele ser el tamaño de la memoria direccionable, por lo que en máquinas de 32 bits 2 32 = 4 GiB (mayor si se utiliza memoria segmentada ) y en máquinas de 64 bits 2 64 = 16 EiB. Así, dado un tamaño limitado, un orden de crecimiento (tiempo o espacio) puede reemplazarse por un factor constante y, en este sentido, todos los algoritmos prácticos son O (1) para una constante lo suficientemente grande o para datos lo suficientemente pequeños.
Esta interpretación es útil principalmente para funciones que crecen extremadamente lentamente: el logaritmo iterado (binario) (log * ) es menor que 5 para todos los datos prácticos (2 65536 bits); (binario) log-log (log log n ) es menor que 6 para prácticamente todos los datos prácticos (2 64 bits); y el log binario (log n ) es menor que 64 para prácticamente todos los datos prácticos (2 x 64 bits). No obstante, un algoritmo con complejidad no constante puede ser más eficiente que un algoritmo con complejidad constante en datos prácticos si la sobrecarga del algoritmo de tiempo constante da como resultado un factor constante mayor, por ejemplo, se puede tener tanto tiempo como y .
Para datos grandes no se pueden ignorar factores lineales o cuadráticos, pero para datos pequeños un algoritmo asintóticamente ineficiente puede ser más eficiente. Esto se usa particularmente en algoritmos híbridos , como Timsort , que usan un algoritmo asintóticamente eficiente (aquí ordenación por fusión , con complejidad temporal ), pero cambian a un algoritmo asintóticamente ineficiente (aquí ordenación por inserción , con complejidad temporal ) para datos pequeños, como el más simple. El algoritmo es más rápido con datos pequeños.