Análisis De Algoritmos

TALLER 4. ANÁLISIS Y EVALUACIÓN DE ALGORITMOS
El análisis de algoritmos es una parte importante de la Teoría de complejidad computacional (rama de la teoría de la computación que estudia, de manera teórica, los recursos requeridos durante el cómputo de un algoritmo para resolver un problema) más amplia, que provee estimaciones teóricas para los recursos que necesita cualquier algoritmo queresuelva un problema computacional dado. Estas estimaciones resultan ser bastante útiles en la búsqueda de algoritmos eficientes. Al momento de realizar un análisis teórico de algoritmos es común calcular su complejidad en un sentido asintótico, es decir, para un tamaño de entrada suficientemente grande. La cota superior asintótica (función que sirve de cota superior de otra función cuando el argumentotiende a infinito), y las notaciones omega (utilizada para manejar la cota inferior del tiempo de ejecución) y theta (utiliza para indicar el orden exacto de complejidad (en el caso de que exista )) se usan con esa finalidad. Por ejemplo, la búsqueda binaria se ejecuta en una cantidad de pasos proporcional a un logaritmo, en O(log(n)). Normalmente las estimaciones asintóticas se utilizan porquediferentes implementaciones del mismo algoritmo no tienen porque tener la misma eficiencia. No obstante la eficiencia de dos implementaciones "razonables" cualesquiera de un algoritmo dado están relacionadas por una constante multiplicativa llamada constante oculta. La notación 0 se utiliza para manejar la complejidad de un algoritmo, es decir, la cota superior del tiempo de ejecución. Estanotación ignora los factores constantes, es decir, ignora si se hace una mejor o peor implementación del algoritmo, además de ser independiente de los datos de entrada del algoritmo. Es decir, la utilidad de aplicar esta notación a un algoritmo es encontrar un límite superior del tiempo de ejecución, es decir, el peor caso. El tiempo de ejecución de un programa se expresa normalmente utilizando lanotación 0 como por ejemplo:

1.- El número medio de instrucciones máquina que genera un compilador determinado. 2.- El número medio de instrucciones por máquina por segundo que ejecuto una computadora específica. Los que influyen en la complejidad tamaño del problema, es la magnitud que al incrementar y al aumentar la complejidad del algoritmo pueden hacer un tiempo de espera más tardado. Ejemplos:1.- Al encender un auto en la mañana se tiene que dejar calentando por un buen tiempo para que no tenga problemas al andar por la calle es un tiempo de ejecución tardado pero es necesario para que no tengas pérdida de tiempo (inconvenientes) más adelante. 2.- El tiempo de ejecución que se necesita para cargar un programa a la computadora, dicho tiempo puede variar según el tamaño del programa.Propiedades de la notación O c O(f(n)) = O(f(n)) O(f(n)+g(n)) = max{ O(f(n)), O(g(n)) } O(f(n)+g(n)) = O(f(n)+g(n)) O(f(n))O(g(n)) = O(f(n)g(n)) O(O(f(n))) = O(f(n))

El tiempo de ejecución de un algoritmo depende de tres factores: 1. El tamaño de los datos de entrada. 2. El contenido de los datos de entrada. 3. El código generado por el compilador y el computador concretos utilizados. Este últimofactor no se suele tener en cuenta. Además, el tiempo de resolución no es fijo para un tamaño de entrada dado. Se pueden definir tres tiempos: 1. Un tiempo mínimo, para el conjunto de entrada más “favorable” (mejor caso). 2. Un tiempo promedio (caso promedio). 3. Un tiempo máximo, para el peor caso posible (peor caso). El mejor caso, es aquél en el que el algoritmo utiliza la menor cantidad derecursos (tiempo, por ejemplo) para solucionar el problema; mientras que el peor caso es aquel en el que el algoritmo utiliza la mayor cantidad de recursos para encontrar la solución. Aunque se diga el mejor caso, no significa que haya una, y sólo una, entrada para la cual el algoritmo se ejecuta en el menor tiempo posible. Un argumento similar se tiene para el peor caso. Por ejemplo para el...