Algoritmos

Tema 01: Fundamentos del Análisis Asintótico de Algoritmos

Noviembre, 2003

CS0218: Algoritmos y Programación II

Introducción

En Ciencias de la Computación se presenta con frecuencia la situación de analizar dos o más algoritmos que resuelven el mismo problema para determinar cuál de ellos requiere menos recursos. Los enfoques para resolver este problema son los siguientes:Benchmarking Análisis Matemático de Algoritmos Análisis Asintótico de Algoritmos

CS0218: Algoritmos y Programación II

1

Introducción

El análisis de algoritmos tiene los siguientes objetivos: Mejorar (si fuese posible) las características estructurales de los algoritmos Facilitar el proceso de selección de un algoritmo (entre varios disponibles) para un problema Predecir la cantidad de recursosrequeridos por un algoritmo para la resolución de un problema

CS0218: Algoritmos y Programación II

2

Introducción

Los principales criterios para realizar el análisis de algoritmos son los siguientes: Correctitud Cantidad de trabajo realizado Cantidad de espacio utilizado Simplicidad “Optimalidad”
CS0218: Algoritmos y Programación II 3

Introducción

Énfasis en la cantidad detrabajo realizado por un algoritmo: Permite determinar la eficiencia del método utilizado por un algoritmo para la resolución de un problema Permite comparar dos o más algoritmos en términos de eficiencia, por lo que debe facilitar el proceso de selección de un algoritmo (entre varios disponibles) para la resolución de un problema Es independiente del computador, del lenguaje de programación, de lashabilidades del programador y de los detalles de implementación

CS0218: Algoritmos y Programación II

4

Benchmarking
Consiste en implementar los algoritmos en cuestión, ejecutarlos y determinar cuál de ellos requiere menos recursos. Esta solución parece ser la más sencilla e intuitiva, sin embargo tiene varios inconvenientes: Pueden existir muchos algoritmos para resolver un mismoproblema, y resulta muy costoso y tedioso implementarlos todos para poder llevar a cabo la comparación. Es una técnica muy específica, ya que determina el desempeño de un programa particular dependiendo de varios factores: el computador, el lenguaje de programación, el compilador, las habilidades del programador y el conjunto de datos de entrada. A partir de un benchmark es difícil predecir elcomportamiento de un programa en otro ambiente.
CS0218: Algoritmos y Programación II 5

Análisis Matemático de Algoritmos

Consiste en tratar de asociar con cada algoritmo una función matemática exacta que mida su “eficiencia” dependiendo sólo de los siguientes factores: Las características estructurales del algoritmo. El tamaño del conjunto de datos de entrada: El número de datos con los cuales trabajael algoritmo. Esta medida se interpreta según el tipo de algoritmo sobre el cual se esté trabajando. Se define la función TA(n) como la cantidad de trabajo realizado por el algoritmo A para procesar una entrada de tamaño n y producir una solución al problema.
CS0218: Algoritmos y Programación II 6

Análisis Matemático de Algoritmos

El análisis matemático de algoritmos es independiente de laimplementación, sin embargo tiene varios inconvenientes: La imposibilidad de determinar, para muchos problemas y cada una de las posibles entradas, la cantidad de trabajo realizado La dificultad para determinar TA(n) exactamente.

CS0218: Algoritmos y Programación II

7

Análisis Asintótico de Algoritmos

Técnica derivada del análisis matemático de algoritmos basada en dos conceptosfundamentales: la caracterización de datos de entrada y la complejidad asintótica. Peor caso: Los casos de datos de entrada que maximizan la cantidad de trabajo realizado por un algoritmo. Mejor caso: Los casos de datos de entrada que minimizan la cantidad de trabajo realizado por un algoritmo. Caso promedio: El valor medio de la cantidad de trabajo realizado por un algoritmo. Se debe tener en cuenta...