Análisis de algoritmos

Para buscar una entrada dada en una lista ordenada dada, tanto el algoritmo binario como el algoritmo de búsqueda lineal (que ignora el pedido) pueden ser utilizados. El análisis del antiguo y del último algoritmo muestra que toma al máximo log₂ n y n pasos de verificación, respectivamente, para una lista de tamaño n. En la lista de ejemplos representados del tamaño 33, buscando "Morin, Arthur" toma 5 y 28 pasos con binario (Mostrar en cyan) y linear (magenta) búsqueda, respectivamente.

Gráficos de funciones utilizadas comúnmente en el análisis de algoritmos, mostrando el número de operaciones N versus 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 de tiempo) o la cantidad de ubicaciones de almacenamiento que utiliza (su complejidad de espacio). 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 pueden ser todas 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 necesarios para 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 proporcional al logaritmo del tamaño n de la lista ordenada que se está buscando, o en O(log n), coloquialmente "en logarítmico tiempo". Por lo general, se utilizan estimaciones asintóticas porque diferentes implementaciones del mismo algoritmo pueden diferir en eficiencia. Sin embargo, las eficiencias de cualquiera de los dos "razonables" Las implementaciones de un algoritmo dado están relacionadas por un factor multiplicativo constante llamado constante oculta.

Las medidas exactas (no asintóticas) de eficiencia a veces se pueden calcular, pero generalmente requieren ciertos supuestos relacionados con 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, p. 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 elementos n, y podemos garantiza que cada búsqueda de un elemento en la lista se puede hacer en la unidad de tiempo, entonces como máximo log₂(n) + 1 se necesitan unidades de tiempo para devolver una respuesta.

Modelos de costes

Las estimaciones de eficiencia de 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é limitado por una constante. Uno debe tener cuidado aquí; por ejemplo, algunos análisis cuentan una 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 adición es constante.

Por lo general, se utilizan dos modelos de costos:

• el modelo uniforme de costos, también llamado medición de los costos uniformes (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 coste logarítmico, también llamado medición de costos logarítmicos (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 que sería ingenuamente 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 del tiempo de ejecución (o tiempo de ejecución o tiempo de ejecución) de un algoritmo como su tamaño de entrada (generalmente indicado como n) aumenta. La eficiencia del 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 usar 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 del análisis del 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 ejecuta un sistema operativo arbitrario), existen inconvenientes significativos adicionales al utilizar un enfoque empírico para medir el rendimiento comparativo de un conjunto dado de algoritmos.

Tome como ejemplo un programa que busca una entrada específica en una lista ordenada de tamaño n. Suponga 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 podrían ser similares a las siguientes:

Según 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 un error:

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. Cuadruplicar 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 aparentemente es 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 muestra una tasa de crecimiento del orden de una función matemática si supera un determinado tamaño de entrada n, la función f(n) veces 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 algunos n₀ y una constante c, el tiempo de ejecución de ese algoritmo nunca será mayor que c × f (n). Este concepto se expresa con frecuencia 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 el tamaño de entrada, se puede decir que la ordenación por inserción es del orden O(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 quicksort es O(n²), pero el tiempo de ejecución promedio de casos es O(n registro 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 tomando medidas empíricas de tiempo {t₁, t₂} en algún 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, 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 de hecho sigue la regla de la 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 de se 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 la comparación de 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 siguiendo la regla de la 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 locales de crecimiento 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 obtener un número entero positivo de la entrada2 si n √° 10
3 impresión "Esto podría tardar un tiempo..."
4 para i = 1 a n
5 para j) 1 a i
6 impresión i
7 impresión "¡Done!"

Una computadora determinada tardará una cantidad discreta de tiempo en ejecutar cada una de las instrucciones involucradas en la realización de este algoritmo. La cantidad específica de tiempo para llevar a cabo una instrucción determinada variará según la instrucción que se esté ejecutando y la computadora que la esté ejecutando, pero en una computadora convencional, esta cantidad será determinista. Digamos que se considera que las acciones realizadas en el paso 1 consumen el tiempo T₁, el paso 2 usa 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:

T1+T2+T3+T7.{displaystyle T_{1}+T_{2}+T_{3}+T_{7}

Los bucles de los pasos 4, 5 y 6 son más complicados de evaluar. Se ejecutará la prueba de bucle externo en el paso 4 (n + 1) veces (tenga en cuenta que se requiere un paso adicional para terminar el ciclo for, por lo tanto, n + 1 y no n ejecuciones), lo que consumirá T₄(n + 1) tiempo. El ciclo interno, por otro lado, se rige por el valor de j, que itera de 1 a i. En la primera pasada por el bucle exterior, j itera de 1 a 1: el bucle interior hace una pasada, por lo que ejecutar el cuerpo del bucle interior (paso 6) consume T₆ tiempo, y la prueba de bucle interno (paso 5) consume 2T₅ tiempo. Durante el siguiente paso por el ciclo externo, j itera de 1 a 2: el ciclo interno realiza dos pasos, por lo que ejecutar el cuerpo del ciclo interno (paso 6) consume 2T₆ tiempo, y la prueba de bucle interno (paso 5) consume 3T₅ tiempo.

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

T6+2T6+3T6+⋯ ⋯ +()n− − 1)T6+nT6{displaystyle T_{6}+2T_{6}+3T_{6}+cdots +(n-1)T_{6}+nT_{6}}

que se puede factorizar como

[1+2+3+⋯ ⋯ +()n− − 1)+n]T6=[12()n2+n)]T6{displaystyle left[1+2+3+cdots +(n-1)+nright]T_{6}=left[{frac {1}{2}}(n^{2}+n)right]T_{6}}

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

2T5+3T5+4T5+⋯ ⋯ +()n− − 1)T5+nT5+()n+1)T5=T5+2T5+3T5+4T5+⋯ ⋯ +()n− − 1)T5+nT5+()n+1)T5− − T5{displaystyle {begin{aligned} limit2T_{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

T5[1+2+3+⋯ ⋯ +()n− − 1)+n+()n+1)]− − T5=[12()n2+n)]T5+()n+1)T5− − T5=[12()n2+n)]T5+nT5=[12()n2+3n)]T5{displaystyle {begin{aligned} limite_{5}left[1+2+3+cdots +(n-1)+n+(n+1)right]-T_{5}= limite[{c {1}{2} {2}+n)right]T_{5}+(n+1) T_{5}-T_{5}nt]T_{5}+nT_{5}\=}ccn} {c} {2} {2} {2}+n)}T_{5}+nT_{5}c}c} {c} {c} {cH}} {c}} {c}}}}} {c}}}}} {c}}}}}} {c}}}}c}}}}}}}} {cc}}}}}}}}}cccc}}}cccccccc}}}}c}}}}}}cc}}}}ccccccccccc}c}}}c}}}cccc}}}}c}c}c}}}}cc}

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

f()n)=T1+T2+T3+T7+()n+1)T4+[12()n2+n)]T6+[12()n2+3n)]T5{fnMicrosoft Sans Serif} {fnMicrosoft Sans Serif} {fn]} {fnMicroc {2}} {fn} {c} {fn} {fn0}fn}fn}fn} {fn} {fn}ccH0} {fn}}} {fn}}}}}}}}}fn}ccccfn}}}}}ccccccccccccH00}}cccccccccccH3}}}}}}ccccccH00}cH00cccccH3}}}}}}cccH00}}}}}}cccH00}}}}}}}}}

que se reduce a

f()n)=[12()n2+n)]T6+[12()n2+3n)]T5+()n+1)T4+T1+T2+T3+T7{fn} {fn}(n^{2}+3n)right]T_{6}+left [{frac {1}{2} {2} {2} {2}+3n)right]T_{5}+(n+1)T_{4}+T_{1}{1}+T_{2}+0}

Como regla empírica, se puede suponer que el término de mayor orden 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 demostrar de la siguiente manera:

Probar eso [12()n2+n)]T6+[12()n2+3n)]T5+()n+1)T4+T1+T2+T3+T7≤ ≤ cn2,n≥ ≥ n0{fnMicrosoft Sans Serif}(n^{2}+n)right]T_{6}+left [{frac {1}{2} {2}(n^{2}+3n)right]T_{5}+(n+1)T_{4}+T_{1}+T_{2}+T_{3}7} No.

[12()n2+n)]T6+[12()n2+3n)]T5+()n+1)T4+T1+T2+T3+T7≤ ≤ ()n2+n)T6+()n2+3n)T5+()n+1)T4+T1+T2+T3+T7()paran≥ ≥ 0){cHFF} {cHFF} {cH00}} {cH00}} {cH00}}} {cH00}} {cH0} {ccH0} {cH0}cH00}cH00}cH00}cH00}cH00}cH00}cH0}}

Vamos k ser una constante mayor o igual a [T₁..T₇]

T6()n2+n)+T5()n2+3n)+()n+1)T4+T1+T2+T3+T7≤ ≤ k()n2+n)+k()n2+3n)+kn+5k=2kn2+5kn+5k≤ ≤ 2kn2+5kn2+5kn2()paran≥ ≥ 1)=12kn2{2}+0} {2}+0}cH0}

Por lo tanto [12()n2+n)]T6+[12()n2+3n)]T5+()n+1)T4+T1+T2+T3+T7≤ ≤ cn2,n≥ ≥ n0parac=12k,n0=1{fnfn} {fnfnfnfnfnfnfn1} {fnfn} {fn0}nccH00}cH00}fnfn}cccH0}cccH00cH0}ccH0}cH00cH00cH0}cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00cH00}cH00cH00cH00cH00cH00cH00}cH00cH00cH00}cH00cH00cH00cH00cH00}cH00cH0}cH00cH00cH0}cH00cH00}cH00cH00 }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 para estos pasos. Esto significaría que el tiempo de ejecución del algoritmo se divide de la siguiente manera:

4+.. i=1ni≤ ≤ 4+.. i=1nn=4+n2≤ ≤ 5n2()paran≥ ≥ 1)=O()n2).{displaystyle 4+sum ¿Qué? ¿Qué? 5n^{2} ({text{for }ngeq 1)=O(n^{2}). }

Análisis de 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 administra ese programa:

mientras archivo sigue abierto: Deja n = tamaño del archivo para cada 100.000 kilobytes de aumento en tamaño de archivo doble 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 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 sensibles al tiempo, 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 poco económica de poder de cómputo o almacenamiento para ejecutarse, lo que nuevamente lo vuelve prácticamente inútil.

Factores constantes

El análisis de algoritmos generalmente se enfoca en el rendimiento asintótico, particularmente en el nivel elemental, pero en las 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 usa 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 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 fundamentalmente útil para las funciones que crecen muy lentamente: (binario) logaritmo iterado (log^*) es menos de 5 para todos los datos prácticos (2⁶⁵⁵³⁶ bits); (binary) log-log (log log n) es menos de 6 para prácticamente todos los datos prácticos (2⁶⁴ bits); y registro binario (log n) es menos de 64 para prácticamente todos los datos prácticos (2⁶⁴ bits). Un algoritmo con complejidad no constante puede ser, sin embargo, más eficiente que un algoritmo con complejidad constante en los datos prácticos si la parte superior del algoritmo de tiempo constante resulta en un factor constante más grande, por ejemplo, uno puede tener klog log n}" xmlns="http://www.w3.org/1998/Math/MathML">K■klog⁡ ⁡ log⁡ ⁡ n{displaystyle K títuloklog log n}klog log n" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/3e92d63ad8925f9548ea045d5d1b165fc4bb6cc6" style="vertical-align: -0.671ex; width:14.875ex; height:2.509ex;"/> tan largo como 6}" xmlns="http://www.w3.org/1998/Math/MathML">K/k■6{displaystyle K/k]6" aria-hidden="true" class="mwe-math-fallback-image-inline" src="https://wikimedia.org/api/rest_v1/media/math/render/svg/7f984b786988572539827baa466ef140fd07204f" style="vertical-align: -0.838ex; width:8.701ex; height:2.843ex;"/> y <math alttext="{displaystyle nn.226=264{displaystyle n made2^{2^{6}=2^{64}<img alt="n.

Para factores lineales o cuadráticos de datos grandes no se puede ignorar, pero para datos pequeños un algoritmo asintotically inefficient puede ser más eficiente. Esto se utiliza particularmente en algoritmos híbridos, como Timsort, que utilizan un algoritmo asintotically eficiente (aquí merge tipo, con complejidad del tiempo nlog⁡ ⁡ n{displaystyle nlog n}), pero cambiar a un algoritmo asintoticamente ineficiente (here tipo de inserción, con la complejidad del tiempo n2{displaystyle n^{2}) para datos pequeños, ya que el algoritmo más simple es más rápido en datos pequeños.