Problema, mientras que la aplicación de Maestro Teorema de

Question

He leído sobre el maestro teorema para la resolución de recurrencias en la Introducción a los Algoritmos, pero tiene un problema (probablemente, debido a la incomprensión), mientras que su aplicación en algunos casos. Por ejemplo, después de recurrencia $T(n) = 5 T(\frac{n}{3}) + \Theta(n^2 \log n)$ y el intento de aplicar este teorema tengo: $a=5; b=3; f(n)=\Theta(n^2 \log n)$. Así, el tercer caso ($f(n)=\Omega(n^{\log_b a + \varepsilon})$) del teorema parece ser el adecuado, si $f(n)$ es regular (es decir,$a f(\frac{n}{b}) \leq c f(n), c < 1$). Pero como yo lo entiendo, $f(n) = \Theta(n^2 \log n)$ no implica la regularidad de $f(n)$ y el maestro teorema es imposible de aplicar en este caso. No he entendido bien?

P. S.: El maestro teorema de sí se expresa por ejemplo en http://www.csail.mit.edu/~thies/6.046-web/master.pdf

Answer 1

Suponiendo que los hechos dados en la pregunta, por lo $n$ lo suficientemente grande como tenemos $k_1 g(n) \leq f(n) \leq k_2 g(n)$ donde $g(n) = n^2 \log n$. Debido a $g(n)$ es regular, podemos aplicar el teorema maestro y nos da el mismo resultado para ambos $k_1 g(n)$$k_2 g(n)$. Desde $f(n)$ es acotada entre las dos funciones, obtenemos el maestro resultado emparedados. Por lo tanto, en el caso 3 para $f(n) = \Theta g(n)$ $g(n)$ regular podemos muy bien suponer $f(n) = g(n)$.

Los problemas sólo puede ocurrir en el caso 2, debido a la delicada interacción de la fusión y la recursividad (que son tanto los efectos de la misma orden).