Complejidad de algoritmos

1.1 CONCEPTO DE COMPLEJIDAD DE ALGORITMOS
Análisis del algoritmo
El análisis de algoritmos es una herramienta para hacer la evaluación de un diseño que permite establecer la calidad de un programa y compararlo con otros programas que resuelven un mismo problema estudiando desde el punto de vista teórico, los recursos computacionales que necesita la ejecución de un programa de ordenador: sueficiencia. Por ejemplo: Tiempo de CPU, Uso de memoria, ancho de banda, etc…
Una solución que pareciera más fácil sería la elaboración e implementación de dos programas que resuelvan el mismo problema y medir el tiempo que cada uno de ellos consume para resolver el problema. Modificar los datos de entrada, promediar al final su desempeño para establecer su comportamiento en el caso promedio. Elproblema que existe con esta solución es sin duda la diversidad de algoritmos que pueden existir para resolver el problema, además de que es costoso y casi imposible implementar todos los programas.
Es por ello que el objetivo que se tiene al analizar algoritmos es establecer una medida de la calidad de los algoritmos, que permita compararlos sin la necesidad de implementarlos.
Esto implica asociara cada algoritmo una función matemática que mida su eficiencia. Además del tiempo de ejecución, para medir la eficiencia se debe considerar la cantidad de memoria utilizada por el programa.
Análisis de la complejidad de algoritmos
El objetivo de este tema es determinar cómo se ha de medir la complejidad de un algoritmo, de forma que sea posible compararlo con otros que resuelven el mismoproblema y decidir cuál de todos ellos es más eficiente. La complejidad de un algoritmo viene dada por los recursos que consume de la computadora: tiempo del procesador y espacio de memoria necesarios para ejecutar el algoritmo. Un algoritmo será tanto más eficiente cuantos menos recursos consuma. Una computadora rápida no es suficiente si no se dispone de un algoritmo eficiente.
No obstante, laeficiencia suele contraponerse a la claridad del código, es decir, una mayor eficiencia suele suponer una menor comprensibilidad del código. Además, un algoritmo eficiente requiere un mayor tiempo de desarrollo. Por tanto, es mejor desarrollar rápidamente en primer lugar un algoritmo claro, aunque sea ineficiente, y optimizarlo posteriormente.
En ocasiones puede no interesarnos buscar el algoritmomás eficiente que resuelve un problema, como por ejemplo si se va a ejecutar pocas veces o con datos de entrada de pequeño tamaño.
Un algoritmo será más eficiente comparado con otro, siempre que consuma menos recursos, como el tiempo y espacio de memoria necesarios para ejecutarlo.
La eficiencia de un algoritmo puede ser cuantificada con las siguientes medidas de complejidad:
Complejidad Temporalo Tiempo de ejecución: Tiempo de cómputo necesario para ejecutar algún programa.
Complejidad espacial: Memoria que utiliza un programa para su ejecución, La eficiencia en memoria de un algoritmo indica la cantidad de espacio requerido para ejecutar el algoritmo; es decir, el espacio en memoria que ocupan todas las variables propias al algoritmo. Para calcular la memoria estática de un algoritmose suma la memoria que ocupan las variables declaradas en el algoritmo. Para el caso de la memoria dinámica, el cálculo no es tan simple ya que, este depende de cada ejecución del algoritmo.
Este análisis se basa en las Complejidades Temporales, con este fin, para cada problema determinaremos una medida N, que llamaremos tamaño de la entrada o número de datos a procesar por el programa,intentaremos hallar respuestas en función de dicha N.
El concepto exacto que cuantifica N dependerá de la naturaleza del problema, si hablamos de un array se puede ver a N como el rango del array, para una matriz, el número de elementos que la componen; para un grafo, podría ser el número de nodos o arcos que lo arman, no se puede establecer una regla para N, pues cada problema acarrea su propia lógica...