Como muchos temas en el área de la computación, cuando se discute sobre alguno de ellos existen conceptos que se deben entender o conocer para facilitar la comunicación y expresar una idea más técnica al respecto.
El análisis de algoritmos forma parte de la Teoría de Complejidad Computacional. Este se encarga de la estimación del tiempo y espacio necesario para ejecutar un algoritmo. Su objetivo principal consiste en establecer una medida de calidad de los algoritmos y permita ser analizado sin necesidad de ser implementado aún. Para una comprensión más amplia del tema, es importante tener en cuenta y conocer ciertos conceptos relacionados.
En el estudio de la teoría, enfocándose en el análisis de algoritmos, han surgido una cantidad de conceptos que describen o identifican el comportamiento de un algoritmo.
Algoritmo: Conjunto de instrucciones en orden que llevan a cabo una o varias acciones para obtener un resultado.
Análisis Teórico: Es un estudio previo a la implementación de un algoritmo. Puede servir para evitar la implementación si el algoritmo es poco eficiente. Se aplica en la etapa de diseño de algoritmos y puede evitar una implementación laboriosa.
Análisis Experimental: Se estudian las estadísticas de tiempo y espacio consumidas por el algoritmo mientras se ejecuta.
Eficiencia de un algoritmo: La cantidad de recursos de cómputo que requiere; es decir, cuál es su tiempo de ejecución y que cantidad de memoria utiliza.
Complejidad en Tiempo: Es el análisis del tiempo utilizado para solucionar un problema de tamaño particular. Esta puede ser expresada en términos del número de operaciones usadas en el algoritmo: comparaciones, suma, división, multiplicación, entre otras. Depende del tamaño de la entrada.
Complejidad en Espacio: Es el análisis de la cantidad de memoria necesaria para solucionar un problema. Al igual que la complejidad en tiempo, la complejidad espacial también depende del tamaño de la entrada.
Mejor caso: Es el tiempo mínimo necesario para ejecutar un algoritmo.
Peor caso: Es el tiempo máximo necesario para ejecutar un algoritmo.
Caso promedio: Es el tiempo promedio necesario para ejecutar un algoritmo.
El análisis de algoritmos es un paso muy relevante a la hora del diseño e implementación de algoritmos para tener en cuenta el tiempo y el espacio que estos toman al ejecutarse. Se hace un estudio para determinar si hay otras posibilidades que den mejores resultados y que consuman menos memoria o bien sacrificar alguna de estas dos variables para obtener un resultado en concreto.
Referencias
Brassard, G., & Bratley, P. (2000). Fundamentos de Algoritmia. Upper Saddle River, NJ, Estados Unidos: Prentice Hall.
Mina, E. A. D. (2016, 13 junio). Analisis Algoritmo. Recuperado 13 de noviembre de 2020, de https://es.slideshare.net/estediaz/analisis-algoritmo
Duch, A. (2007, marzo). Análisis de Algoritmos. Recuperado de https://www.cs.upc.edu/~duch/home/duch/analisis.pdf
Velasco, M. L. (2010, 20 febrero). Análisis De Algoritmos. Recuperado 13 de noviembre de 2020, de https://es.slideshare.net/mluisavel/anlisis-de-algoritmos1-3234499