Análisis de algoritmos

Dado que los algoritmos son independientes de la plataforma (es decir, un algoritmo determinado puede implementarse en un lenguaje de programación arbitrario en un ordenador arbitrario que ejecute un sistema operativo arbitrario ), existen inconvenientes significativos adicionales al utilizar un enfoque empírico para evaluar 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 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 de rendimiento en ambas computadoras ejecutando sus respectivos programas podrían ser similares a las siguientes:

Basándonos en estas métricas, sería fácil llegar a la conclusión de que el ordenador A ejecuta un algoritmo mucho más eficiente que el del ordenador B. Sin embargo, si se aumenta el tamaño de la lista de entrada a un número suficiente, se demuestra de forma contundente que dicha conclusión es errónea:

El ordenador A, que ejecuta el programa de búsqueda lineal, presenta una tasa de crecimiento lineal . El tiempo de ejecución del programa es directamente proporcional al tamaño de su entrada. Duplicar el tamaño de la entrada duplica el tiempo de ejecución, cuadruplicarlo también, y así sucesivamente. Por otro lado, el ordenador B, que ejecuta el programa de búsqueda binaria, presenta una tasa de crecimiento logarítmica . Cuadruplicar el tamaño de la entrada solo aumenta el tiempo de ejecución en una cantidad constante (en este ejemplo, 50 000 ns). Aunque el ordenador A sea aparentemente más rápido, el ordenador B inevitablemente lo superará en tiempo de ejecución, ya que ejecuta un algoritmo con una tasa de crecimiento mucho menor.

De manera informal, se puede decir que un algoritmo presenta 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 dicho algoritmo. En otras palabras, para un tamaño de entrada n dado 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 utilizando la notación Big O. Por ejemplo, dado que el tiempo de ejecución del algoritmo de ordenación por inserción crece cuadráticamente a medida que aumenta ^el tamaño de su entrada, se puede decir que este algoritmo es de orden O ( n² ) .

La notación Big O es una forma conveniente de expresar el peor escenario posible para un algoritmo dado, 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 ) .

Suponiendo que el tiempo de ejecución sigue la regla de potencia, t ≈ kn ^a , el parámetro a se puede encontrar ^{[ 9 ]} tomando mediciones empíricas del tiempo de ejecución t ₁ y t ₂ en algunos puntos de tamaño del problema n ₁ y n ₂ , y resolviendo la ecuación t ₂ / t ₁ = ( n ₂ / n ₁ ) ^a con respecto a a , es decir, a = log( t ₂ / t ₁ )/log( n ₂ / n ₁ ) . En otras palabras, esto mide la pendiente de la línea empírica en el gráfico log-log del tiempo de ejecución frente al tamaño de entrada, en algún punto de tamaño. Si el orden de crecimiento sigue efectivamente la regla de potencia (y por lo tanto la línea en el gráfico log-log es efectivamente 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 puede servir para comparar dos algoritmos cualesquiera dados en cuanto a sus órdenes locales empíricos de comportamiento de crecimiento. Aplicado a la tabla anterior:

Se observa claramente que el primer algoritmo presenta un crecimiento lineal, siguiendo efectivamente la regla de potencia. Los valores empíricos del segundo disminuyen rápidamente, lo que sugiere que sigue otra regla de crecimiento y, en cualquier caso, presenta órdenes de crecimiento locales mucho menores (y que siguen mejorando), empíricamente, que el primero.

La complejidad temporal de un algoritmo en el peor de los casos puede evaluarse a veces examinando su estructura y haciendo algunas suposiciones simplificadoras. Considere el siguiente pseudocódigo :

1. Obtener un número entero positivo n de la entrada . 2. Si n > 10, 3. Imprimir "Esto podría tardar un poco..." 4 para i = 1 a n 5 para j = 1 a i 6 imprimir i * j 7 imprimir "¡Hecho!"

Un ordenador determinado tardará una cantidad de tiempo discreta en ejecutar cada una de las instrucciones de este algoritmo. Digamos que las acciones del paso ₁ consumen como máximo T₁ , el paso 2 consume 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 en el peor de los casos, se debe asumir que el paso 3 también se ejecutará. Por lo tanto, el tiempo total 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 la primera pasada por el 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 ₅ tiempo. Durante la siguiente pasada por el bucle externo, j itera de 1 a 2: el bucle interno hace dos pasadas, 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 conjunto, 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 ser factorizado ^{[ 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 forma 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}}}$

lo cual puede ser factorizado 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 cual 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 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:

Demuestra 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{para }}n\geq 0)\end{aligned}}}$

Sea k una constante mayor o igual que [ T ₁ .. T ₇ ]. ${\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{para }}n\geq 1)=12kn^{2}\end{aligned}}}$ Por lo tanto${\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{ para }}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 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}).}$

La metodología de análisis en tiempo de ejecución también puede utilizarse para predecir otras tasas de crecimiento, como el consumo de espacio de memoria . Como ejemplo, consideremos el siguiente pseudocódigo que gestiona y reasigna el uso de memoria por parte de un programa en función del tamaño de un archivo que dicho programa gestiona:

Mientras el archivo permanezca abierto: sea n = tamaño del archivo. Por cada 100.000 kilobytes de aumento en el tamaño del archivo, se duplica 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 , del orden de O (2 ⁿ ) . Esta es una tasa de crecimiento extremadamente rápida y probablemente inmanejable para el consumo de recursos de memoria .