DAA - Análisis de algoritmos
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. El termino"analysis of algorithms" fue acuñado por Donald Knuth.
El análisis de algoritmos es una parte importante de la teoría de la complejidad computacional, que proporciona una estimación teórica de los recursos necesarios de un algoritmo para resolver un problema computacional específico. La mayoría de los algoritmos están diseñados para trabajar con entradas de longitud arbitraria. El análisis de algoritmos es la determinación de la cantidad de tiempo y recursos espaciales necesarios para ejecutarlo.
Por lo general, la eficiencia o el tiempo de ejecución de un algoritmo se establece como una función que relaciona la longitud de entrada con el número de pasos, conocida como time complexity, o volumen de memoria, conocido como space complexity.
La necesidad de análisis
En este capítulo, discutiremos la necesidad de análisis de algoritmos y cómo elegir un algoritmo mejor para un problema en particular, ya que un problema computacional puede resolverse mediante diferentes algoritmos.
Al considerar un algoritmo para un problema específico, podemos comenzar a desarrollar el reconocimiento de patrones para que tipos similares de problemas puedan resolverse con la ayuda de este algoritmo.
Los algoritmos suelen ser bastante diferentes entre sí, aunque el objetivo de estos algoritmos es el mismo. Por ejemplo, sabemos que un conjunto de números se puede ordenar utilizando diferentes algoritmos. El número de comparaciones realizadas por un algoritmo puede variar con otros para la misma entrada. Por lo tanto, la complejidad temporal de esos algoritmos puede diferir. Al mismo tiempo, necesitamos calcular el espacio de memoria requerido por cada algoritmo.
El análisis del algoritmo es el proceso de analizar la capacidad de resolución de problemas del algoritmo en términos de tiempo y tamaño requerido (el tamaño de la memoria para el almacenamiento durante la implementación). Sin embargo, la principal preocupación del análisis de algoritmos es el tiempo o el rendimiento requeridos. Generalmente, realizamos los siguientes tipos de análisis:
Worst-case - El número máximo de pasos realizados en cualquier instancia de tamaño a.
Best-case - El número mínimo de pasos realizados en cualquier instancia de tamaño a.
Average case - Un número medio de pasos realizados en cualquier instancia de tamaño. a.
Amortized - Una secuencia de operaciones aplicadas a la entrada de tamaño. a promediado en el tiempo.
Para resolver un problema, debemos considerar el tiempo y la complejidad del espacio, ya que el programa puede ejecutarse en un sistema donde la memoria es limitada pero hay suficiente espacio disponible o puede ser viceversa. En este contexto, si comparamosbubble sort y merge sort. La clasificación de burbujas no requiere memoria adicional, pero la clasificación por combinación requiere espacio adicional. Aunque la complejidad temporal de la clasificación de burbujas es mayor en comparación con la clasificación por fusión, es posible que necesitemos aplicar la clasificación de burbujas si el programa necesita ejecutarse en un entorno donde la memoria es muy limitada.