Análisis de algoritmos
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 la longitud 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 un crecimiento en el tamaño de la entrada. Diferentes entradas de la misma longitud pueden hacer que el algoritmo tenga un comportamiento diferente, por lo queLas descripciones de casos mejores, peores y medios 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 la complejidad computacional más amplia , que proporciona estimaciones teóricas de los recursos que necesita 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 proporcionales al logaritmo de la longitud 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 implementacionesdel mismo algoritmo puede diferir en eficiencia. Sin embargo, las eficiencias de dos implementaciones "razonables" 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 ciertos supuestos relacionados con la implementación particular del algoritmo, llamado modelo de cálculo . Un modelo de cálculo puede definirse en términos de una computadora abstracta , por ejemplo, una 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 , se necesitan log 2 n + 1 unidades de tiempo para devolver una respuesta.
Las estimaciones de eficiencia del 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é acotado por encima de 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 por una sola suma sea constante.
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 .
