1 Análisis y Diseño de AlgoritmosMétodo de Sustitución Método de Iteración Teorema Maestro Método de la Ecuación Característica

2 Análisis y Diseño de AlgoritmosÁrboles de Recursión, visualizando la Iteración

3 Análisis y Diseño de Algoritmos

4 Análisis y Diseño de Algoritmos

5 Análisis y Diseño de Algoritmos

6 Análisis y Diseño de Algoritmos

7 Análisis y Diseño de Algoritmos

8 Análisis y Diseño de Algoritmos

9 Análisis y Diseño de Algoritmos

10 Análisis y Diseño de Algoritmos

11 Análisis y Diseño de AlgoritmosMétodo de la Ecuación Característica

12 Análisis y Diseño de Algoritmos1.- Recurrencias Homogéneas Se aplica para problemas en que T (n) = C1 T ( n–1 ) + C2 T ( n–2 ) Cn T ( n–k )

13 Análisis y Diseño de AlgoritmosEjemplo de Aplicación Ecuación Característica Homogénea Fibonacci (n) Inicio Si n = = 1 o n = = 2 entonces devolver 1 Sino devolver Fibonacci ( n-1 ) + Fibonacci ( n-2 ) Fin T (n) = T ( n-1 ) + T ( n-2 ) Fin Fibonacci

14 Análisis y Diseño de Algoritmos

15 Análisis y Diseño de Algoritmos

16 Análisis y Diseño de Algoritmos

17 Análisis y Diseño de Algoritmos

18 Análisis y Diseño de Algoritmos1.- Recurrencias No Homogéneas T (n) = C1 T ( n-1 ) + C2 T ( n-2 ) Ck T ( n-k ) + b p(n) (**) b es una constante p(n) es un polinomio de grado d. Generalizando, para resolver (**), es suficiente tomar la siguiente ecuación característica (a0xk +a1xk ak)(x-b)d+1=0

19 Análisis y Diseño de Algoritmos

20 Análisis y Diseño de Algoritmos