¿Cómo puedo resolver la relación de recurrencia $T(n) = 2T(n/2) + n\log n$ ? Casi coincide con el Teorema del Maestro, excepto por el $n\log n$ parte.
Tomemos $n = 2^m$ . Entonces tenemos la recurrencia $$T(2^m) = 2T(2^{m-1}) + 2^m \log_2(2^m) = 2T(2^{m-1}) + m 2^m$$ Llamando a $T(2^m)$ como $f(m)$ , obtenemos que \begin {align} f(m) & = 2 f(m-1) + m 2^m \\ & = 2(2f(m-2) + (m-1)2^{m-1}) + m2^m \\ & = 4f(m-2) + (m-1)2^m + m2^m \\ & = 4(2f(m-3) +(m-2)2^{m-2}) + (m-1)2^m + m2^m \\ & = 8f(m-3) +(m-2)2^m + (m-1)2^m + m2^m \\ \end {align} Procediendo en estas líneas, obtenemos que \begin {align} f(m) &= 2^m f(0) + 2^m (1+2+3+ \cdots +m) = 2^m f(0) + \dfrac {m(m+1)}{2}2^m \\ & = 2^m f(0) + m(m+1)2^{m-1} \end {align} Por lo tanto, $T(n) = n T(1) + n \left(\dfrac{\log_2(n) (1+\log_2(n))}{2} \right) = \mathcal{\Theta}(n \log^2 n)$ .
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
el problema dado se ajusta mejor al teorema maestro
1 votos
Pregunta similar en cs.SE .
0 votos
Satisface el Caso 2 del Teorema Maestro Caso 2: f(n) = Theta O(n^log_b(a) (log_2(n))^k ) para algún k >= 0 T(n) = O(n^log_b(a) (log_2(n))^(k+1) ) En nuestro caso f(n) = n^(log_2(2)) (log n) ^ 1, Por lo tanto k = 1 T(n) = Theta O(n (log_2(n) ) ^ 2)
0 votos
El teorema maestro no cubre los casos en los que la función de la izquierda no es un polinomio. n log n está acotado por n^2, pero entonces no da un límite theta.