En este tutorial, aprenderá qué es el teorema maestro y cómo se usa para resolver relaciones de recurrencia.
El método maestro es una fórmula para resolver relaciones de recurrencia de la forma:
T (n) = aT (n / b) + f (n), donde, n = tamaño de la entrada a = número de subproblemas en la recursividad n / b = tamaño de cada subproblema. Se supone que todos los subproblemas tienen el mismo tamaño. f (n) = costo del trabajo realizado fuera de la llamada recursiva, que incluye el costo de dividir el problema y el costo de fusionar las soluciones. función.
Una función asintóticamente positiva significa que para un valor suficientemente grande de n, tenemos f(n)> 0.
El teorema maestro se utiliza para calcular la complejidad temporal de las relaciones de recurrencia (algoritmos de divide y vencerás) de una manera simple y rápida.
Teorema maestro
Si a ≧ 1y b> 1son constantes y f(n)es una función asintóticamente positiva, entonces la complejidad temporal de una relación recursiva viene dada por
T (n) = aT (n / b) + f (n) donde, T (n) tiene los siguientes límites asintóticos: 1. Si f (n) = O (n log b a-ϵ ), entonces T (n ) = Θ (n log b a ). 2. Si f (n) = Θ (n log b a ), entonces T (n) = Θ (n log b a * log n). 3. Si f (n) = Ω (n log b a + ϵ ), entonces T (n) = Θ (f (n)). ϵ> 0 es una constante.
Cada una de las condiciones anteriores se puede interpretar como:
- Si el costo de resolver los subproblemas en cada nivel aumenta en un cierto factor, el valor de
f(n)será polinomialmente menor que . Por lo tanto, la complejidad del tiempo se ve oprimida por el costo del último nivel, es decir.nlogb anlogb a - Si el costo de resolver el subproblema en cada nivel es casi igual, entonces el valor de
f(n)será . Por lo tanto, la complejidad del tiempo será multiplicada por el número total de niveles, es decir.nlogb af(n)nlogb a * log n - Si el costo de resolver los subproblemas en cada nivel disminuye en cierto factor, el valor de
f(n)será polinomialmente mayor que . Así, la complejidad del tiempo se ve oprimida por el costo de .nlogb af(n)
Ejemplo resuelto del teorema maestro
T (n) = 3T (n / 2) + n2 Aquí, a = 3 n / b = n / 2 f (n) = n 2 log b a = log 2 3 ≈ 1.58 <2 es decir. f (n) <n log b a + ϵ , donde, ϵ es una constante. El caso 3 implica aquí. Por lo tanto, T (n) = f (n) = Θ (n 2 )
Limitaciones del teorema maestro
El teorema maestro no se puede utilizar si:
- T (n) no es monótono. p.ej.
T(n) = sin n f(n)no es un polinomio. p.ej.f(n) = 2n- a no es una constante. p.ej.
a = 2n a < 1
