Thursday, March 15, 2012

13 Ejercicios Resueltos paso a paso sobre recursividad usando Teorema Maestro

-->
El teorema maestro proporciona una solución paso a paso para estudiar el comportamiento del tiempo de ejecución de algoritmos que cumplen las siguiente relación de recurrencia:

donde T(n) es el tiempo de ejecución, a ≥ 1 y b >1 son constantes ademas
  • n es el tamaño de todo el problema.
  • a es el número de partes en que se ha dividido el problema original para estudiarlo recursivamente.
  • (n/b) tamaño de cada parte en que se ha dividido el problema, asumiendo el mismo tamaño para cada parte.
  • f(n) es el costo de realizar las llamadas recursivas, incluye el trabajo de dividir el problema y volver a unir las subtotales para obtener la solución total. F(n)  es un función independiente de T(n) y no negativa.
La relación de recurrencia se analiza expandiendo iterativamente el tiempo de ejecución y sustituyéndose en la misma ecuación, para evitar esta expansión se puede determinar un límite asintótico usando la notación de Landau (O grande) usada comúnmente en el análisis algoritmos Divide y vencerás.
Es posible determinar tres tipos de casos asintóticos --> d = logb(a):


Ejemplos Resueltos
Caso 1
T(n)= Θ(nlogb(a)) Si existe alguna constante ε > 0 tal que f(n) ∈ O(nlogb(a) –ᵋ) 


Caso 2
-->
T(n)= Θ(n logb(a) logk+1(n)) Si f(n) Θ(n logb(a) logk(n) ) para cualquier constante k 0

Caso 3
-->
T(n)= Θ(f(n)) SI existe ε> 0 tal que f(n) Ω (nlog b(a) + ε) la segunda condición es que exista alguna constante c < 1 tal que para todo n≥ 1 se cumple que: af(n/b)≤ cf(n)

También te interesa: Ejemplos resueltos sobre analisis iterativo de la complejidad de algoritmos recursivos

Si tienes información adicional sobre este tema, tus comentarios o links de referencia serán bienvenidos.
Post a Comment