Análisis de algoritmos

Estudio de los recursos utilizados por un algoritmo

Para buscar una entrada dada en una lista ordenada dada, se pueden utilizar tanto el algoritmo de búsqueda binaria como el de búsqueda lineal (que ignora el ordenamiento). El análisis del primero y del segundo 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 la 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 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, peor y promedio de los casos 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 . ^[1] El análisis de algoritmos es una parte importante de una teoría de complejidad computacional más amplia , que proporciona estimaciones teóricas de los recursos que necesita cualquier algoritmo que resuelva un problema computacional determinado . Estas estimaciones brindan 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 sentido asintótico, es decir, estimar la función de complejidad para una entrada arbitrariamente grande. 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" cualesquiera 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 ciertas suposiciones sobre la implementación particular del algoritmo, llamada modelo de computación . Un modelo de computación se puede definir en términos de una computadora abstracta , por ejemplo, la máquina de Turing , y/o postulando que ciertas operaciones se ejecutan en la 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 la unidad de tiempo, entonces se necesitan como máximo log ₂ ( n ) + 1 unidades de tiempo para devolver una respuesta.

Modelos de costos

Las estimaciones de eficiencia en términos de tiempo dependen de lo que definamos como un paso. Para que el análisis 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 costes: ^{[3] [4] [5] [6] [7]}

• 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 utilizar, 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 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 se pensaría que es posible. ^[8]

Análisis en tiempo de ejecución

El análisis en tiempo de ejecución es una clasificación teórica que estima y anticipa el aumento del tiempo de ejecución (o 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, 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 del 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 se puede implementar en un lenguaje de programación arbitrario en una computadora arbitraria que ejecute un sistema operativo arbitrario ), existen desventajas significativas adicionales en el uso de 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 implementa en la computadora A, una máquina de última generación, utilizando un algoritmo de búsqueda lineal , y en la computadora B, una máquina mucho más lenta, utilizando un algoritmo de búsqueda binaria . Las pruebas comparativas en las dos computadoras que ejecutan sus respectivos programas podrían verse de la siguiente manera:

Con base en estas métricas, sería fácil llegar a la conclusión de que el ordenador A está ejecutando un algoritmo que es muy superior en eficiencia al del ordenador B. Sin embargo, si el tamaño de la lista de entrada se incrementa a un número suficiente, se demuestra claramente que esa conclusión es errónea:

El ordenador 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 al tamaño de entrada. Si se duplica el tamaño de entrada, se duplica el tiempo de ejecución; si se cuadruplica el tamaño de entrada, se cuadruplica el tiempo de ejecución, y así sucesivamente. Por otro lado, el ordenador B, que ejecuta el programa de búsqueda binaria, muestra una tasa de crecimiento logarítmica . Si se cuadruplica el tamaño de entrada, el tiempo de ejecución solo aumenta en una cantidad constante (en este ejemplo, 50.000 ns). Aunque el ordenador A es ostensiblemente una máquina más rápida, el ordenador B inevitablemente superará al ordenador 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 f ( n ) multiplicada por una constante positiva proporciona un límite superior 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 c × f ( n ) . Este concepto se expresa frecuentemente usando 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 ² ) .

La notación Big O es una forma conveniente de expresar el peor escenario posible para un algoritmo determinado, aunque también se puede utilizar para expresar el caso promedio; por ejemplo, el peor escenario posible para quicksort es O ( n ² ) , pero el tiempo de ejecución del caso promedio 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 ^[9] tomando mediciones 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 modo que a = log( t ₂ / t ₁ )/log( n ₂ / n ₁ ) . En otras palabras, esto mide la pendiente de la línea empírica en el gráfico logarítmico del tiempo de ejecución frente al tamaño de entrada, en algún punto de tamaño. Si el orden de crecimiento sigue de hecho la regla de potencia (y por lo tanto la línea en el gráfico logarítmico es de hecho una línea recta), el valor empírico dese mantendrá 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 locales empíricos de comportamiento de crecimiento. Aplicado a la tabla anterior:

Se ve claramente que el primer algoritmo muestra un orden de crecimiento lineal que, en efecto, sigue la regla de la potencia. Los valores empíricos del segundo disminuyen 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 que mejoran aún más), empíricamente, que el primero.

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

La complejidad en tiempo de ejecución para el peor escenario 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. Obtenga un entero positivo n de la entrada
2 si n > 103. Imprimir "Esto podría tardar un poco..."4 para i = 1 a n5 para j = 1 a i6 imprimir i * j7 imprimir "¡Hecho!"

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 ₁ , el paso 2 utiliza tiempo como máximo T ₂ , y así sucesivamente.

En el algoritmo anterior, los pasos 1, 2 y 7 se ejecutarán solo 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 en los pasos 4, 5 y 6 son más difíciles de evaluar. La prueba del bucle externo en el paso 4 se ejecutará ( n + 1 ) veces, ^[10] lo que consumirá T ₄ ( n + 1 ) tiempo. El bucle interno, por otro lado, está gobernado por el valor de j, que itera de 1 a i . En el primer paso a través del bucle externo, j itera de 1 a 1: El bucle interno hace un pase, 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 ₅ tiempo. Durante el siguiente paso a través del bucle externo, j itera de 1 a 2: el bucle interno hace dos pases, por lo que ejecutar el cuerpo del bucle interno (paso 6) consume 2 T ₆ tiempo, y la prueba del bucle interno (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 puede factorizarse ^[11] 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 puede factorizarse 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 lo 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 de 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:

Demuestre que ${\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 elegido de modo que una unidad sea mayor o igual a los tiempos reales de estos pasos. Esto significaría que el tiempo de ejecución del algoritmo se descompone de la siguiente manera: ^[12]

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

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,  duplicar 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 del orden de O (2 ⁿ ) . Se trata de una tasa de crecimiento extremadamente rápida y, muy probablemente, inmanejable para el consumo de recursos de memoria .

Pertinencia

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 sensibles al tiempo, un algoritmo que tarda demasiado en ejecutarse puede hacer que sus resultados queden obsoletos o sean inútiles. Un algoritmo ineficiente también puede acabar necesitando una cantidad antieconómica de potencia de cálculo o almacenamiento para ejecutarse, lo que lo vuelve prácticamente inútil.

Factores constantes

El análisis de algoritmos se centra típicamente en el rendimiento asintótico, particularmente en el nivel elemental, pero en aplicaciones prácticas los factores constantes son importantes y los datos del mundo real en la práctica siempre tienen un tamaño limitado. El límite es típicamente 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. Por lo tanto, 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 lo suficientemente grande o para datos lo 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); el logaritmo-logaritmo (binario) (log log n ) es menor que 6 para prácticamente todos los datos prácticos (2 ⁶⁴ bits); y el logaritmo 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 siempre que 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 los 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, ya que el algoritmo más simple es más rápido en datos pequeños. ${\displaystyle n\log n}$ ${\displaystyle n^{2}}$

Véase 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 de programas
• 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 la información

Notas

1. "Knuth: Noticias recientes". 28 de agosto de 2016. Archivado desde el original el 28 de agosto de 2016.
2. Cormen, Thomas H., ed. (2009). Introducción a los algoritmos (3.ª ed.). Cambridge, Mass.: MIT Press. pp. 44–52. ISBN 978-0-262-03384-8.OCLC 311310321  .
3. Alfred V. Aho; John E. Hopcroft; Jeffrey D. Ullman (1974). El diseño y análisis de algoritmos informáticos . Addison-Wesley Pub. Co. ISBN 9780201000290., sección 1.3
4. Juraj Hromkovič (2004). Informática teórica: introducción a los autómatas, computabilidad, complejidad, algorítmica, aleatorización, comunicación y criptografía. Springer. pp. 177-178. ISBN 978-3-540-14015-3.
5. Giorgio Ausiello (1999). Complejidad y aproximación: problemas de optimización combinatoria y sus propiedades de aproximación. Springer. pp. 3–8. ISBN 978-3-540-65431-5.
6. Wegener, Ingo (2005), Teoría de la complejidad: explorando los límites de los algoritmos eficientes, Berlín, Nueva York: Springer-Verlag , p. 20, ISBN 978-3-540-21045-0
7. Robert Endre Tarjan (1983). Estructuras de datos y algoritmos de red. SIAM. pp. 3–7. ISBN 978-0-89871-187-5.
8. Ejemplos del precio de la abstracción?, cstheory.stackexchange.com
9. Cómo evitar el abuso de O y los sobornos Archivado el 8 de marzo de 2017 en Wayback Machine , en el blog "La carta perdida de Gödel y P=NP" de RJ Lipton, profesor de Ciencias de la Computación en Georgia Tech, contando una idea de Robert Sedgewick
10. se requiere un paso adicional para finalizar el bucle for, por lo tanto n + 1 y no n ejecuciones
11. Se puede demostrar por inducción que ${\displaystyle 1+2+3+\cdots +(n-1)+n={\frac {n(n+1)}{2}}}$
12. Este enfoque, a diferencia del enfoque anterior, descuida el tiempo constante consumido por las pruebas de bucle que terminan sus respectivos bucles, pero es trivial demostrar que dicha 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 edición). 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 edición). 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, ordenamiento, 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 . Cambridge University Press . ISBN 978-0-521-88473-0.

Enlaces externos

• Medios relacionados con Análisis de algoritmos en Wikimedia Commons