Análisis de algoritmos - Analysis of algorithms

Para buscar una entrada dada en una lista ordenada dado, tanto el binario y la búsqueda lineal algoritmo (que ignora el pedido) se puede utilizar. El análisis del primero y del último algoritmo muestra que se necesitan como máximo log ₂ ( n ) yn pasos de verificación, respectivamente, para obtener una lista de longitud n . En la lista de ejemplo representada de longitud 33, la búsqueda de "Morin, Arthur" toma 5 y 28 pasos con búsqueda binaria (mostrada en cian ) y lineal ( magenta ), respectivamente.

Gráficos de funciones comúnmente utilizadas en el análisis de algoritmos, que muestran el número de operaciones N versus el tamaño de entrada n para cada función.

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 la longitud 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 un crecimiento en el tamaño de la entrada. Diferentes entradas de la misma longitud pueden hacer que el algoritmo tenga un comportamiento diferente, por lo que las descripciones de casos mejores, peores y promedio pueden 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 . 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 que necesita cualquier algoritmo que resuelva un problema computacional dado . Estas estimaciones proporcionan una idea de las direcciones razonables de búsqueda de algoritmos eficientes .

En el análisis teórico de algoritmos, es común estimar su complejidad en el sentido asintótico, es decir, estimar la función de complejidad para una entrada arbitrariamente grande. La notación Big O , la notación Big-omega y la notación Big-theta se utilizan para este fin. Por ejemplo, se dice que la búsqueda binaria se ejecuta en un número de pasos proporcionales al logaritmo de la longitud 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 dado están relacionadas por un factor multiplicativo constante llamado constante oculta .

A veces se pueden calcular medidas exactas (no asintóticas) de eficiencia, pero generalmente requieren ciertos supuestos relacionados con la implementación particular del algoritmo, llamado modelo de cálculo . Un modelo de cálculo puede definirse en términos de una computadora abstracta , por ejemplo, una 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 , se necesitan log ₂ n + 1 unidades de tiempo para devolver una respuesta.

Modelos de costos

Las estimaciones de eficiencia del tiempo dependen de lo que definamos 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é acotado por encima de 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 por una sola suma sea constante.

Generalmente se utilizan dos modelos de costos:

• el modelo de costo uniforme , también llamado medición de costo uniforme (y variaciones similares), asigna un costo constante a cada operación de la máquina, independientemente del tamaño de los números involucrados
• El modelo de costo logarítmico , también llamado medición de costo logarítmico (y variaciones similares), asigna un costo a cada operación de la máquina proporcional al número de bits involucrados.

Este último es más engorroso de usar, por lo que solo se emplea cuando es necesario, por ejemplo, en el análisis de algoritmos aritméticos de precisión arbitraria , como los que se usan 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 podría usar en la práctica y, por lo tanto, hay algoritmos que son más rápidos de lo que sería ingenuamente. pensó posible.

Análisis en tiempo de ejecución

El análisis de 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 el tiempo de ejecución es un tema de gran interés en la informática : un programa puede tardar segundos, horas o incluso años en terminar de ejecutarse, según el 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 solo se puede lograr mediante los métodos teóricos de análisis en tiempo de ejecución.

Deficiencias de las métricas empíricas

Dado que los algoritmos son independientes de la plataforma (es decir, un algoritmo dado se puede implementar en un lenguaje de programación arbitrario en una computadora arbitraria que ejecuta un sistema operativo arbitrario ), existen inconvenientes significativos adicionales al usar un enfoque empírico para medir el rendimiento comparativo de un conjunto dado 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 implementó en la Computadora A, una máquina de última generación, usando un algoritmo de búsqueda lineal , y en la Computadora B, una máquina mucho más lenta, usando un algoritmo de búsqueda binaria . Las pruebas comparativas en las dos computadoras que ejecutan sus respectivos programas pueden tener el siguiente aspecto:

Sobre la base de estas métricas, sería fácil llegar a la conclusión de que el equipo A está ejecutando un algoritmo que es muy superior en eficiencia a la del equipo B . Sin embargo, si el tamaño de la lista de entrada 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, exhibe 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, exhibe 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 está ejecutando un algoritmo con una tasa de crecimiento mucho más lenta.

Órdenes de crecimiento

De manera informal, 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 multiplicada por una constante positiva proporciona un límite superior o límite para el tiempo de ejecución de ese algoritmo. En otras palabras, para un tamaño de entrada dado n mayor que algún n ₀ y una constante c , el tiempo de ejecución de ese algoritmo nunca será mayor que . Este concepto se expresa con frecuencia utilizando la notación Big O. 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 ² ). ${\ Displaystyle f (n)}$${\ Displaystyle c \ times f (n)}$

La notación Big O es una forma conveniente de expresar el peor de los casos para un algoritmo dado, aunque también se puede usar para expresar el caso promedio; por ejemplo, el peor de los casos para la ordenación rápida es O ( n ² ), pero el tiempo de ejecución promedio del caso es O ( n  log  n ) .

Órdenes empíricos de crecimiento

Suponiendo que el tiempo de ejecución sigue la regla de potencia, t ≈ kn ^a , el coeficiente a se puede encontrar tomando medidas empíricas del tiempo de ejecución en algunos puntos del tamaño del problema , y calculando así . En otras palabras, mide la pendiente de la línea empírica en la gráfica logarítmica del tiempo de ejecución frente al tamaño del problema, en algún punto del tamaño. Si el orden de crecimiento sigue de hecho la regla de la potencia (por lo que la línea en la gráfica logarítmica es una línea recta), el valor empírico de a permanecerá constante en diferentes rangos, y si no, cambiará (y la línea es una línea curva), pero aún podría servir para comparar dos algoritmos dados en cuanto a sus órdenes empíricos locales de comportamiento de crecimiento . Aplicado a la tabla anterior: ${\ Displaystyle \ {t_ {1}, t_ {2} \}}$${\ Displaystyle \ {n_ {1}, n_ {2} \}}$${\ Displaystyle t_ {2} / t_ {1} = (n_ {2} / n_ {1}) ^ {a}}$${\ Displaystyle a = \ log (t_ {2} / t_ {1}) / \ log (n_ {2} / n_ {1})}$

Se ve claramente que el primer algoritmo exhibe un orden lineal de crecimiento siguiendo la regla de la potencia. Los valores empíricos para el 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 mejorando aún más), empíricamente, que el primero.

Evaluación de la complejidad del tiempo de ejecución

La complejidad del tiempo de ejecución para el peor de los casos de un algoritmo dado a veces se puede evaluar examinando la estructura del algoritmo y haciendo algunas suposiciones simplificadoras. Considere el siguiente pseudocódigo :

1    get a positive integer n from input
2    if n > 10
3        print "This might take a while..."
4    for i = 1 to n
5        for j = 1 to i
6            print i * j
7    print "Done!"

Una computadora determinada tomará una cantidad de tiempo discreta para ejecutar cada una de las instrucciones involucradas en la ejecución de este algoritmo. La cantidad específica de tiempo para llevar a cabo una instrucción dada variará dependiendo de qué instrucción se esté ejecutando y qué computadora la esté ejecutando, pero en una computadora convencional, esta cantidad será determinista . Digamos que se considera que las acciones llevadas a cabo en el paso 1 consumen tiempo T ₁ , el paso 2 utiliza el tiempo T ₂ , y así sucesivamente.

En el algoritmo anterior, los pasos 1, 2 y 7 solo 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-3 y el paso 7 es:

${\ Displaystyle T_ {1} + T_ {2} + T_ {3} + T_ {7}. \,}$

Los bucles de los pasos 4, 5 y 6 son más difíciles de evaluar. La prueba de bucle externo en el paso 4 se ejecutará ( n + 1) veces (tenga en cuenta que se requiere un paso adicional para terminar el bucle for, por lo tanto, n + 1 y no n ejecuciones), lo que consumirá T ₄ ( n + 1) tiempo . El bucle interno, por otro lado, se rige por el valor de j, que itera de 1 a i . En la primera pasada a través del bucle externo, j itera de 1 a 1: el bucle interno hace una pasada, por lo que ejecutar el cuerpo del bucle interno (paso 6) consume T ₆ tiempo, y la prueba del bucle interno (paso 5) consume 2 T ₅ veces. Durante la siguiente pasada por el bucle exterior, j itera de 1 a 2: el bucle interior hace 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 ₅ tiempo.

En total, el tiempo total necesario para ejecutar el cuerpo del bucle interno se puede expresar como una progresión aritmética :

${\ Displaystyle T_ {6} + 2T_ {6} + 3T_ {6} + \ cdots + (n-1) T_ {6} + nT_ {6}}$

que se puede factorizar como

${\ Displaystyle T_ {6} \ left [1 + 2 + 3 + \ cdots + (n-1) + n \ right] = T_ {6} \ left [{\ frac {1} {2}} (n ^ {2} + n) \ derecha]}$

El tiempo total requerido para ejecutar la prueba del circuito externo se puede evaluar de manera similar:

${\ Displaystyle {\ begin {alineado} & 2T_ {5} + 3T_ {5} + 4T_ {5} + \ cdots + (n-1) T_ {5} + nT_ {5} + (n + 1) T_ {5 } \\ = \ & T_ {5} + 2T_ {5} + 3T_ {5} + 4T_ {5} + \ cdots + (n-1) T_ {5} + nT_ {5} + (n + 1) T_ { 5} -T_ {5} \ end {alineado}}}$

que se puede factorizar como

${\ Displaystyle {\ begin {alineado} & T_ {5} \ left [1 + 2 + 3 + \ cdots + (n-1) + n + (n + 1) \ right] -T_ {5} \\ = & \ izquierda [{\ frac {1} {2}} (n ^ {2} + n) \ right] T_ {5} + (n + 1) T_ {5} -T_ {5} \\ = & T_ {5} \ left [{\ frac {1} {2}} (n ^ {2} + n) \ right] + nT_ {5} \\ = & \ left [{\ frac {1} {2}} (n ^ {2} + 3n) \ right] T_ {5} \ end {alineado}}}$

Por lo tanto, el tiempo de ejecución total de este algoritmo es:

${\ Displaystyle f (n) = T_ {1} + T_ {2} + T_ {3} + T_ {7} + (n + 1) T_ {4} + \ left [{\ frac {1} {2} } (n ^ {2} + n) \ right] T_ {6} + \ left [{\ frac {1} {2}} (n ^ {2} + 3n) \ right] T_ {5}}$

que se reduce a

${\ Displaystyle f (n) = \ left [{\ frac {1} {2}} (n ^ {2} + n) \ right] T_ {6} + \ left [{\ frac {1} {2} } (n ^ {2} + 3n) \ right] T_ {5} + (n + 1) T_ {4} + T_ {1} + T_ {2} + T_ {3} + T_ {7}}$

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 de tiempo de ejecución. En este ejemplo, n ² es el término de mayor orden, por lo que se puede concluir que f (n) = O (n ² ). Formalmente, esto se puede probar de la siguiente manera:

Pruebalo ${\ Displaystyle \ left [{\ frac {1} {2}} (n ^ {2} + n) \ right] T_ {6} + \ left [{\ frac {1} {2}} (n ^ { 2} + 3n) \ right] T_ {5} + (n + 1) T_ {4} + T_ {1} + T_ {2} + T_ {3} + T_ {7} \ leq cn ^ {2}, \ n \ geq n_ {0}}$

${\ Displaystyle {\ begin {alineado} & \ left [{\ frac {1} {2}} (n ^ {2} + n) \ right] T_ {6} + \ left [{\ frac {1} { 2}} (n ^ {2} + 3n) \ right] T_ {5} + (n + 1) T_ {4} + T_ {1} + T_ {2} + T_ {3} + T_ {7} \ \\ leq & (n ^ {2} + n) T_ {6} + (n ^ {2} + 3n) T_ {5} + (n + 1) T_ {4} + T_ {1} + T_ {2 } + T_ {3} + T_ {7} \ ({\ text {para}} n \ geq 0) \ end {alineado}}}$

Sea k una constante mayor o igual que [ T ₁ .. T ₇ ] Por lo tanto

${\ Displaystyle {\ begin {alineado} & T_ {6} (n ^ {2} + n) + T_ {5} (n ^ {2} + 3n) + (n + 1) T_ {4} + T_ {1 } + T_ {2} + T_ {3} + T_ {7} \ leq k (n ^ {2} + n) + k (n ^ {2} + 3n) + kn + 5k \\ = & 2kn ^ {2 } + 5kn + 5k \ leq 2kn ^ {2} + 5kn ^ {2} + 5kn ^ {2} \ ({\ text {for}} n \ geq 1) = 12kn ^ {2} \ end {alineado}} }$

${\ Displaystyle \ left [{\ frac {1} {2}} (n ^ {2} + n) \ right] T_ {6} + \ left [{\ frac {1} {2}} (n ^ { 2} + 3n) \ right] T_ {5} + (n + 1) T_ {4} + T_ {1} + T_ {2} + T_ {3} + T_ {7} \ leq cn ^ {2}, n \ geq n_ {0} {\ text {for}} c = 12k, n_ {0} = 1}$

Un enfoque más elegante para analizar este algoritmo sería declarar que [ T ₁ .. T ₇ ] son ​​todos iguales a una unidad de tiempo, en un sistema de unidades elegido de modo que una unidad sea mayor o igual que los tiempos reales para estos pasos. Esto significaría que el tiempo de ejecución del algoritmo se desglosa de la siguiente manera:

${\ Displaystyle 4+ \ sum _ {i = 1} ^ {n} i \ leq 4+ \ sum _ {i = 1} ^ {n} n = 4 + n ^ {2} \ leq 5n ^ {2} \ ({\ text {para}} n \ geq 1) = O (n ^ {2}).}$

Análisis de la tasa de crecimiento de otros recursos

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 en función del tamaño de un archivo que ese programa administra:

while file is still open:
    let n = size of file
    for every 100,000 kilobytes of increase in file size
        double the amount of memory reserved

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 ⁿ ). Esta es una tasa de crecimiento extremadamente rápida y probablemente inmanejable para el consumo de recursos de memoria .

Relevancia

El análisis de algoritmos es importante en la práctica porque el uso accidental o no intencional 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 sean obsoletos o inútiles. Un algoritmo ineficiente también puede terminar requiriendo una cantidad antieconómica de potencia de cálculo o almacenamiento para funcionar, volviéndolo prácticamente inútil.

Factores constantes

El análisis de algoritmos generalmente se enfoca en el desempeño asintótico, particularmente en el nivel elemental, pero en aplicaciones prácticas los factores constantes son importantes y los datos del mundo real son en la práctica siempre limitados en tamaño. El límite suele ser el tamaño de la memoria direccionable, por lo que en máquinas de ³² bits 2 ³² = 4 GiB (mayor si se usa memoria segmentada ) y en máquinas de ⁶⁴ bits 2 ⁶⁴ = 16 EiB. Así, dado un tamaño limitado, un orden de crecimiento (tiempo o espacio) puede ser reemplazado por un factor constante, y en este sentido todos los algoritmos prácticos son O (1) para una constante suficientemente grande o para datos suficientemente pequeños.

Esta interpretación es principalmente útil para funciones que crecen extremadamente lentamente: el logaritmo iterado (binario) (log ^* ) es menor que 5 para todos los datos prácticos (2 ⁶⁵⁵³⁶ bits); (binario) log-log (log log n ) es menor que 6 para prácticamente todos los datos prácticos (2 ⁶⁴ bits); y el registro binario (log n ) es menor que 64 para prácticamente todos los datos prácticos (2 ⁶⁴ 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, uno puede tener tanto tiempo como y . ${\ Displaystyle K> k \ log \ log n}$${\ Displaystyle K / k> 6}$${\ Displaystyle n <2 ^ {2 ^ {6}} = 2 ^ {64}}$

Para datos grandes, los factores lineales o cuadráticos no pueden ignorarse, 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 de tiempo ), pero cambian a un algoritmo asintóticamente ineficiente (aquí ordenación por inserción , con complejidad de tiempo ) para datos pequeños, como el más simple El algoritmo es más rápido en datos pequeños. ${\ Displaystyle n \ log n}$${\ Displaystyle n ^ {2}}$

Ver también

• Análisis amortizado
• Análisis de algoritmos paralelos
• Complejidad computacional asintótica
• Mejor, peor y promedio caso
• Notación Big O
• Teoría de la complejidad computacional
• Teorema maestro (análisis de algoritmos)
• NP-Completo
• Análisis numérico
• Tiempo polinomial
• Optimización del programa
• Elaboración de perfiles (programación informática)
• Escalabilidad
• Análisis suavizado
• Análisis de terminación : el subproblema de verificar si un programa terminará en absoluto
• Complejidad temporal : incluye una tabla de órdenes de crecimiento para algoritmos comunes.
• Complejidad basada en información

Notas

Referencias

• Sedgewick, Robert ; Flajolet, Philippe (2013). Introducción al análisis de algoritmos (2ª ed.). Addison-Wesley. ISBN 978-0-321-90575-8.
• Greene, Daniel A .; Knuth, Donald E. (1982). Matemáticas para el análisis de algoritmos (Segunda ed.). Birkhäuser. ISBN 3-7643-3102-X.
• Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L. y Stein, Clifford (2001). Introducción a los algoritmos . Capítulo 1: Fundamentos (Segunda ed.). Cambridge, MA: MIT Press y McGraw-Hill. págs. 3–122. ISBN 0-262-03293-7.
• Sedgewick, Robert (1998). Algoritmos en C, Partes 1-4: Fundamentos, Estructuras de datos, Clasificación, Búsqueda (3ª ed.). Reading, MA: Addison-Wesley Professional. ISBN 978-0-201-31452-6.
• Knuth, Donald . El arte de la programación informática . Addison-Wesley.
• Goldreich, Oded (2010). Complejidad computacional: una perspectiva conceptual . Prensa de la Universidad de Cambridge . ISBN 978-0-521-88473-0.

enlaces externos

• Medios relacionados con el análisis de algoritmos en Wikimedia Commons