Análisis de algoritmos.

Estudio de los recursos utilizados por un algoritmo.

Para buscar una entrada determinada en una lista ordenada determinada, se pueden utilizar tanto el algoritmo de búsqueda binario como el lineal (que ignora el orden). El análisis del primero y del último algoritmo muestra que se necesitan como máximo log ₂ n y n pasos de verificación, respectivamente, para una lista de tamaño n . En la lista de ejemplo de tamaño 33 que se muestra, la búsqueda de "Morin, Arthur" requiere 5 y 28 pasos con búsqueda binaria (que se muestra 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 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 del mejor, el peor y el promedio de los casos 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 . 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 son log ₂ ( n ) + 1 unidades de tiempo. necesario para devolver una respuesta.

Modelos de costos

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: ^{[2] [3] [4] [5] [6]}

• El modelo de costo uniforme , también llamado modelo de costo unitario (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 complicado de usar, 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. ^[7]

Análisis en tiempo de ejecución

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.

Deficiencias de las métricas empíricas

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.

Órdenes de crecimiento

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 ₀ 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 ² ) .

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 ² ) , pero el tiempo de ejecución promedio del caso es O ( n log n ) .

Órdenes empíricas de crecimiento.

Suponiendo que el tiempo de ejecución sigue la regla de potencia, t ≈ kn ^a , el coeficiente a se puede encontrar ^[8] tomando medidas empíricas del tiempo de ejecución { t ₁ , t ₂ } en algunos puntos del tamaño del problema { n ₁ , n ₂ }, y calculando t ₂ / t ₁ = ( n ₂ / n ₁ ) ^a de manera que a = log( t ₂ / t ₁ )/log( n ₂ / n ₁ ) . 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.

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

La complejidad en 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 discreta de tiempo 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 ₁ , el paso 2 utiliza tiempo como máximo T ₂ , 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:

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

Los bucles de los pasos 4, 5 y 6 son más complicados de evaluar. La prueba del bucle externo en el paso 4 se ejecutará ( n + 1) veces, ^[9] lo que consumirá T ₄ ( 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 ₆ tiempo, y la prueba del bucle interno (paso 5) consume 2 T ₅ 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 ₆ de tiempo, y la prueba del bucle interior (paso 5) consume 3 T ₅ veces.

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 ^[10] como

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

El tiempo total necesario para ejecutar la prueba del bucle interno se puede evaluar de manera similar:

${\displaystyle {\begin{aligned}&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{aligned}}}$

que se puede factorizar como

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

Por tanto, el tiempo total de ejecución 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}}$

lo 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 en el tiempo de ejecución. En este ejemplo, n ² es el término de orden más alto, por lo que se puede concluir que f ( n ) = O ( n ² ) . Formalmente esto se puede demostrar 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{aligned}&\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{for }}n\geq 0)\end{aligned}}}$

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

${\displaystyle {\begin{aligned}&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{aligned}}}$

${\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 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: ^[11]

${\displaystyle 4+\sum _{i=1}^{n}i\leq 4+\sum _{i=1}^{n}n=4+n^{2}\leq 5n^{2}\ ({\text{for }}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 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 ⁿ ) . Se trata de una tasa de crecimiento extremadamente rápida y probablemente inmanejable del consumo de recursos de memoria .

Relevancia

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 sean 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.

Factores constantes

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 ³² = 4 GiB (mayor si se utiliza memoria segmentada ) y en máquinas de 64 bits 2 ⁶⁴ = 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 ⁶⁵⁵³⁶ bits); (binario) log-log (log log n ) es menor que 6 para prácticamente todos los datos prácticos (2 ⁶⁴ 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, 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 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. ${\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 de los casos
• Notación O grande
• 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 comprobar si un programa terminará
• Complejidad del tiempo : incluye una tabla de órdenes de crecimiento para algoritmos comunes
• Complejidad basada en la información

Notas

1. "Knuth: noticias recientes". 28 de agosto de 2016. Archivado desde el original el 28 de agosto de 2016.
2. Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). El diseño y análisis de algoritmos informáticos . Pub Addison-Wesley. ISBN del condado 9780201000290., sección 1.3
3. Juraj Hromkovič (2004). Informática teórica: introducción a los autómatas, computabilidad, complejidad, algorítmica, aleatorización, comunicación y criptografía. Saltador. págs. 177-178. ISBN 978-3-540-14015-3.
4. Giorgio Ausiello (1999). Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximación. Saltador. págs. 3–8. ISBN 978-3-540-65431-5.
5. Wegener, Ingo (2005), Teoría de la complejidad: exploración de los límites de los algoritmos eficientes, Berlín, Nueva York: Springer-Verlag , p. 20, ISBN 978-3-540-21045-0
6. Robert Endre Tarjan (1983). Estructuras de datos y algoritmos de red. SIAM. págs. 3–7. ISBN 978-0-89871-187-5.
7. Ejemplos del precio de la abstracción?, cstheory.stackexchange.com
8. Cómo evitar el abuso de O y los sobornos Archivado el 8 de marzo de 2017 en Wayback Machine , en el blog "Gödel's Lost Letter and P=NP" de RJ Lipton, profesor de Ciencias de la Computación en Georgia Tech, relatando la idea de Robert Sedgewick
9. se requiere un paso adicional para terminar el bucle for, por lo tanto n + 1 y no n ejecuciones
10. Se puede demostrar por inducción que ${\displaystyle 1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}}$
11. Este enfoque, a diferencia del enfoque anterior, ignora el tiempo constante consumido por las pruebas de bucle que terminan sus respectivos bucles, pero es trivial demostrar que tal omisión no afecta el resultado final.

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 a 4: fundamentos, estructuras de datos, clasificación, búsqueda (3ª ed.). Reading, MA: Addison-Wesley Profesional. 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 Análisis de algoritmos en Wikimedia Commons