Análisis de algoritmos

El término análisis de algoritmos fue acuñado por Donald Knuth^[1] y se refiere al proceso de encontrar la complejidad computacional de un algoritmo que resuelva un problema computacional dado, con el objetivo de proveer estimaciones teóricas de los recursos que necesita. Usualmente, los recursos a los cuales se hace referencia son el tiempo (complejidad temporal) y el almacenamiento (complejidad espacial). Mientras que la complejidad temporal involucra determinar una función que relaciona la longitud o el tamaño de la entrada del algoritmo con el número de pasos que realiza, la complejidad espacial busca la cantidad de ubicaciones de almacenamiento que utiliza. Distintos algoritmos pueden utilizarse para resolver un mismo problema y a su vez los algoritmos pueden estudiarse de forma independiente del lenguaje de programación a utilizar y de la máquina donde se ejecutará.^[2] Esto significa que se necesitan técnicas que permitan comparar la eficiencia de los algoritmos antes de su implementación.

Análisis de la complejidad temporal

Este análisis es conocido también con el nombre de análisis del tiempo de ejecución. A continuación, se presenta una explicación intuitiva utilizando el ejemplo del algoritmo de búsqueda para luego profundizar en forma más teórica.

Punto de vista intuitivo

Si se piensa en el problema de encontrar una clave en un conjunto de registros ubicados dentro de un vector devolviendo la posición donde se encuentra, se tienen distintos algoritmos de búsquedas que se pueden aplicar. El más sencillo es la búsqueda secuencial pero si el conjunto de elementos se encuentran ordenados (según su clave) dentro del vector se podría aplicar la búsqueda binaria. De este ejemplo se pueden sacar varias conclusiones.

Por un lado, dependiendo el algoritmo utilizado el proceso de búsqueda será más o menos eficiente en el sentido de cantidad de comparaciones realizadas. Por ejemplo, según la Figura 1 para buscar "Morin, Arthur" la búsqueda secuencial debe realizar 28 comparaciones mientras que la búsqueda binaria realiza solo 5 comparaciones. Esto confirma que para la resolución de un determinado problema existe más de un algoritmo y que estos suelen tener distintos niveles de eficiencia, necesitándose una forma de elegirlos antes de programarlos como se mencionó en la introducción.

Si se continúa analizando la búsqueda secuencial y si la intención es encontrar a "Zeeman, Pieter" se deben realizar 33 comparaciones pero si se intenta encontrar a "Abt, Antal" solo dos comparaciones son necesarias. Es decir, si se busca el último elemento la cantidad de comparaciones es equivalente a n, donde n es la cantidad de elementos presentes en el vector; pero por otro, también depende de la clave a buscar. En consecuencia, la cantidad de comparaciones necesarias depende de la cantidad de elementos que posea el vector y su orden; y del elemento a buscar, esto es, depende de las entradas del algoritmo. De aquí se puede concluir que para analizar el tiempo de ejecución se podría contar la cantidad de comparaciones realizadas y se la multiplica por el tiempo requerido por cada comparación.

Pero aquí se presenta otro inconveniente ¿el tiempo que toma una comparación depende de la computadora en donde se esté ejecutando? Sería conveniente encontrar una función que dado el tamaño de entrada acote los pasos realizados por el algoritmo para encontrar la solución en un tiempo que dependa de una constante C que representa el tiempo en diferentes computadoras.

Análisis de los distintos casos

**Figura 2**: Representación gráfica de los tres casos analizados dentro de la complejidad temporal de un algoritmo.

Diferentes entradas de la misma longitud pueden causar que el algoritmo se comporte distinto, por lo que se podría analizar el algoritmo desde tres perspectivas: el mejor caso, el caso promedio y el peor caso.^[3] En la Figura 2 se muestra dichos casos de manera gráfica.

Mejor caso: es la función definida por el número mínimo de pasos dados en cualquier instancia de tamaño n. Representa la curva más baja en el gráfico (verde) y se denomina cota inferior.

Caso promedio: es la función definida por el número promedio de pasos dados en cualquier instancia de tamaño n.

Peor caso: es la función definida por el número máximo de pasos dados en cualquier instancia de tamaño n. Esto representa la curva que pasa por el punto más alto en el gráfico (rojo) y se denomina cota superior.

Cuando no se especifica lo contrario, la función que describe el rendimiento de un algoritmo suele este caso, dado que este caso garantiza que el algoritmo no tardará mayor cantidad de tiempo, es decir acota superiormente la cantidad de pasos.

Punto de vista teórico

Análisis asintótico

A la hora de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica, y las notaciones omega (cota inferior) y theta (caso promedio) se usan con esa finalidad. Por ejemplo, la búsqueda binaria decimos que se ejecuta en una cantidad de pasos proporcional a un logaritmo, en $O(log(n))$ , coloquialmente "en tiempo logarítmico". Normalmente, las estimaciones asintóticas se utilizan porque diferentes implementaciones del mismo algoritmo no tienen por qué tener la misma eficiencia. No obstante, la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta.

Órdenes de crecimiento

Artículo principal: Cota superior asintótica

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 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_{0}$ y una constante $c$ , el tiempo de ejecución de ese algoritmo nunca será mayor que $f(n)$ . Este concepto se expresa con frecuencia utilizando la notación O Grande, que brinda una forma conveniente de expresar el peor de los casos para un algoritmo dado.

Por ejemplo, el ordenamiento por inserción crece cuadráticamente a medida que aumenta su tamaño de entrada, entonces se puede decir que este tipo de ordenamiento es del orden de n cuadrado, en notación O Grande sería: $O(n^{2})$ . Otro tipo de funciones que pueden ser utilizadas para acotar un algoritmo son las mostradas en la Figura 3.

Análisis no asintótico

La medida exacta (no asintótica) de la eficiencia a veces puede ser computada, pero para ello suele hacer falta aceptar supuestos acerca de la implementación concreta del algoritmo, llamada modelo de computación. Un modelo de computación puede definirse en términos de un ordenador abstracto, como la Máquina de Turing, y/o postulando que ciertas operaciones se ejecutan en una unidad de tiempo. Por ejemplo, si al conjunto ordenado al que aplicamos una búsqueda binaria tiene $n$ elementos, y podemos garantizar que una única búsqueda binaria puede realizarse en un tiempo unitario, entonces se requieren, como mucho, $log_{2}N+1$ unidades de tiempo para devolver una respuesta.

Las medidas exactas de eficiencia son útiles para quienes verdaderamente implementan y usan algoritmos porque tienen más precisión y, así, les permite saber cuánto tiempo pueden suponer que tomará la ejecución. Para algunas personas, como los desarrolladores de videojuegos, una constante oculta puede significar la diferencia entre éxito y fracaso.

Las estimaciones de tiempo dependen de cómo definamos un paso. Para que el análisis tenga sentido, debemos garantizar que el tiempo requerido para realizar un paso se encuentra acotado superiormente por una constante. Hay que mantenerse precavido en este terreno; por ejemplo, algunos análisis cuentan con que la suma de dos números se hace en un paso. Este supuesto puede no estar garantizado en ciertos contextos. Si, por ejemplo, los números involucrados en la computación pueden ser arbitrariamente grandes, dejamos de poder asumir que la adición requiere un tiempo constante (usando papel y lápiz, compara el tiempo que necesitas para sumar dos enteros de 2 dígitos cada uno y el necesario para hacerlo con dos enteros pero de 1000 dígitos cada uno).

Relevancia

En la práctica el análisis de algoritmos es importante porque el uso accidental o no intencional de un algoritmo ineficiente puede afectar significativamente el rendimiento de un sistema. En aplicaciones de tiempo real, 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.

Véase también

Referencias

↑ Knuth, Donald (1997). The Art of Computer Programming. Estados Unidos: Addison-Wesley. Consultado el 14 de septiembre de 2021.
↑ Skiena, Steve S. The Algorithm Design Manual (Second edición). Springer International Publishing. p. 742. ISBN 978-1-84800-069-8.
↑ Sedgewick, Robert; Flajolet, Philippe (1996). An Introduction to the Analysis of Algorithms. Estados Unidos: Addison-Wesley. Consultado el 2013.

Bibliografía

Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Chapter 1: Foundations, pp.3–122.
Gilles Brassard & Paul Bratley. Fundamentos de algoritmia. (ISBN 84-89660-00-X)
Greene, Daniel A.; Knuth, Donald E. (1982). Mathematics for the Analysis of Algorithms (Second ed.). Birkhäuser. ISBN 3-7643-3102-X.

Datos: Q333464

[1] Knuth, Donald (1997). The Art of Computer Programming. Estados Unidos: Addison-Wesley. Consultado el 14 de septiembre de 2021.

[2] Skiena, Steve S. The Algorithm Design Manual (Second edición). Springer International Publishing. p. 742. ISBN 978-1-84800-069-8.

[3] Sedgewick, Robert; Flajolet, Philippe (1996). An Introduction to the Analysis of Algorithms. Estados Unidos: Addison-Wesley. Consultado el 2013.

[1]

[2]

[3]