Eficiencia de algoritmos

Análisis de Eficiencia de los  Algoritmos

Indice
• • • • Introducción Midiendo la Eficiencia de los Algoritmos Notación Asintótica Reglas para el Cálculo de la Eficiencia de los Algoritmos –Funciones no recursivas – Funciones Recursivas • Solución de Ecuaciones de Recurrencia – Sustitución – Inducción – Árbol de Recursión – Fórmula Maestra – Ecuación Característica

Introducción• Objetivo: analizar la eficiencia de un algoritmo en función del  tamaño de la entrada.  • Ventajas: – Mejor Comprensión de los algoritmos  – Diseñar algoritmos mejores –Determinas la escalabilidad • Depende – El problema que tratamos de resolver  – El lenguaje de programación utilizado  – El compilador  – El hardware utilizado  – La habilidad del programador 

Análisis de Eficiencia• Empírica • Teórica estamos interesados en contar cuantas instrucciones  simples (asignaciones, comparaciones, etc.) se ejecutan,   asumimos que independientemente de la máquina en que se ejecute, todas las operaciones simples  consumen el mismo tiempo. Principio de Invarianza: Dos implementaciones distintas de un mismo algoritmo  no difieren en eficiencia más que en una constante multiplicativa.

Tipos de Análisis
• Peor de los Casos: Se corresponde con el peor tiempo. T(n)  es el tiempo máximo sobre las entradas.  • Mejor Caso: Límite inferior en el tiempo. T(n) es el menor tiempo de  todas las posibles entradas • Caso Promedio: Es el tiempo medio esperado sobre todas  las posibles entradas de tamaño n. Se considera una distribución de probabilidad sobre las entradas.   • Análisis Probabilístico:  Es el tiempo de ejecución esperado  para una entrada aleatoria. Se expresa tanto el tiempo de  ejecución y la probabilidad de obtenerlo. •Análisis Amortizado: El tiempo que se obtiene para un  conjunto de ejecuciones, dividido por el número de  ejecuciones. 

Notación Asintótica
• Estudia el comportamiento del algoritmo cuando el tamaño ...