Eficiencia De Los Algoritmos

EFICIENCIA Y COMPLEJIDAD

1

Una vez que 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. Siempre que se trata de resolver un problema, puede interesar considerar distintos algoritmos, con el fin de utilizar elmás eficiente. Pero, ¿cómo determinar cuál es "el mejor"?. La estrategia empírica consiste en programar los algoritmos y ejecutarlos en un computador sobre algunos ejemplares de prueba. La estrategia teórica consiste en determinar matemáticamente la cantidad de recursos (tiempo, espacio, etc.) que necesitará el algoritmo en función del tamaño del ejemplar considerado.
2

Un algoritmo es eficientecuando logra llegar a sus objetivos planteados utilizando la menor cantidad de recursos posibles, es decir, minimizando el uso memoria, de pasos y de esfuerzo humano. La eficiencia de un programa tiene dos ingredientes fundamentales: espacio y tiempo. · La eficiencia en espacio es una medida de la cantidad de memoria requerida por un programa. · La eficiencia en tiempo se mide en términos de lacantidad de tiempo de ejecución del programa. Ambas dependen del tipo de computador y compilador, por lo que solo estudiaremos la eficiencia de los algoritmos.

3

La calidad de un algoritmo puede ser avalada utilizando varios criterios. Uno de los criterios más importantes es el tiempo utilizado en la ejecución del algoritmo. Existen varios aspectos a considerar en cada criterio de tiempo.Uno de ellos está relacionado con el tiempo de ejecución requerido por los diferentes algoritmos, para encontrar la solución final de un problema o cálculo particular. Normalmente, un problema se puede resolver por métodos distintos, con diferentes grados de eficiencia.

Cuando se usa una computadora es importante limitar el consumo de recursos.

4

Recurso Tiempo: · Aplicaciones informáticasque trabajan “en tiempo real” requieren que los cálculos se realicen en el menor tiempo posible. · Aplicaciones que manejan un gran volumen de información si no se tratan adecuadamente pueden necesitar tiempos impracticables. Recurso Memoria: · Las máquinas tienen una memoria limitada.

5

El tiempo de ejecución de un algoritmo va a depender de diversos factores como son: los datos deentrada 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 concreto que 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 eltiempo 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 de ejecución del algoritmo para unos valores de entrada dados y en una computadora concreta.
6

El Análisis A Priori (o teórico) entrega una función que limita el tiempo de cálculo de un algoritmo. Consiste en obtener una expresión que indiqueel comportamiento del algoritmo en función de los parámetros que influyan. · Es aplicable en la etapa de diseño de los algoritmos, constituyendo uno de los factores fundamentales a tener en cuenta. En la Prueba A Posteriori (experimental o empírica) se recogen estadísticas de tiempo y espacio consumidas por el algoritmo mientras se ejecuta.
7

Denotaremos por T(n) el tiempo de ejecución de unalgoritmo para una entrada de tamaño n.

Teóricamente T(n) debe indicar el número de instrucciones ejecutadas por una computadora ideal. Debemos buscar por tanto medidas simples y abstractas, independientes de la computadora 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...