ANALISIS DE ALGORITMOS
En informática cuando se dice que un problema tiene solución, significa que existe un algoritmo susceptible de implantarse en una computadora, capaz de producir la respuesta correcta para cualquier instancia del problema en cuestión.
En algunas ocasiones es posible encontrar más de un algoritmo capaz de resolver un problema planteado, lo cual nos enfrenta al problemade escoger alguno de ellos. La tarea de decidir cuál de ellos es el mejor debe basarse en criterios acordes a nuestros intereses. En la mayoría de los casos la elección de un buen algoritmo está orientada hacia la disminución del costo que implica la solución del problema; bajo este enfoque es posible dividir los criterios en dos clases:
a) Criterios orientados a minimizar el costo de desarrollo:claridad, sencillez
Y facilidad de implantación, depuración y mantenimiento.
b) Criterios orientados a disminuir el costo de ejecución: tiempo de procesador
Y cantidad de memoria utilizados.
Los recursos que consume un algoritmo pueden estimarse mediante herramientas
Teóricas y constituyen, por lo tanto, una base contable para la elección de un algoritmo. En las Ciencias de la Computación,la actividad dedicada a determinar la cantidad de recursos que consumen los algoritmos se le denomina análisis de algoritmos.
EFICIENCIA DE UN ALGORITMO
Una vez dispongamos de un algoritmo que funciona correctamente, es necesario definir criterios para medir su rendimiento o comportamiento. Estos criterios se centran principalmente en su simplicidad y en el uso eficiente de los recursos.Respecto al uso eficiente de los recursos, éste suele medirse en función de dos parámetros: el espacio, es decir, memoria que utiliza, y el tiempo, lo que tarda en ejecutarse. Ambos representan los costes que supone encontrar la solución al problema planteado mediante un algoritmo. Dichos parámetros van a servir además para comparar algoritmos entre sí, permitiendo determinar el más adecuado deentre varios que solucionan un mismo problema. En este capítulo nos centraremos solamente en la eficiencia temporal.
El tiempo de ejecución de un algoritmo va a depender de diversos factores como son: los datos de entrada que le suministremos, la calidad del código generado por el compilador para crear el programa objeto, la naturaleza y rapidez de las instrucciones máquina del procesador concretoque ejecute el programa, y la complejidad intrínseca del algoritmo. Hay dos estudios posibles sobre el tiempo:
1. Uno que proporciona una medida teórica (a priori), que consiste en obtener una función que acote (por arriba o por abajo) el tiempo de ejecución del algoritmo para unos valores de entrada dados.
2. Y otro que ofrece una medida real (a posteriori), consistente en medir el tiempo deejecución del algoritmo para unos valores de entrada dados y en un ordenador concreto.
Ambas medidas son importantes puesto que, si bien la primera nos ofrece estimaciones del comportamiento de los algoritmos de forma independiente del ordenador en donde serán implementados y sin necesidad de ejecutarlos, la segunda representa las medidas reales del comportamiento del algoritmo. Estas medidas sonfunciones temporales de los datos de entrada.
La unidad de tiempo a la que debe hacer referencia estas medidas de eficiencia no puede ser expresada en segundos o en otra unidad de tiempo concreta, pues no existe un ordenador estándar al que puedan hacer referencia todas las medidas. Denotaremos por T(n) el tiempo de ejecución de un algoritmo para una entrada de tamaño n.
Teóricamente T(n)debe indicar el número de instrucciones ejecutadas por un ordenador idealizado. Debemos buscar por tanto medidas simples y abstractas, independientes del ordenador a utilizar. Para ello es necesario acotar de alguna forma la diferencia que se puede producir entre distintas implementaciones de un mismo algoritmo, ya sea del mismo código ejecutado por dos máquinas de distinta velocidad, como de dos…
