-
Mtodo de SustitucinMtodo de IteracinTeorema MaestroMtodo de la
Ecuacin Caracterstica
Anlisis y Diseo de Algoritmos
-
rboles de Recursin, visualizando la Iteracin Anlisis y Diseo de
Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Mtodo de la Ecuacin Caracterstica
Anlisis y Diseo de Algoritmos
-
1.- Recurrencias Homogneas
Se aplica para problemas en que T (n) = C1 T ( n1 ) + C2 T ( n2
) + ... + Cn T ( nk )
Anlisis y Diseo de Algoritmos
-
Ejemplo de Aplicacin Ecuacin Caracterstica Homognea Fibonacci
(n) InicioSi 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 FibonacciAnlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
1.- Recurrencias No Homogneas
T (n) = C1 T ( n-1 ) + C2 T ( n-2 ) + ... + Ck T ( n-k ) + b
p(n) (**)
b es una constantep(n) es un polinomio de grado d.Generalizando,
para resolver (**), es suficiente tomar la siguiente ecuacin
caracterstica
(a0xk +a1xk-1+...+ak)(x-b)d+1=0Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
-
Anlisis y Diseo de Algoritmos
