Resolver T (n) = 2T (n / 2) + log n con el método del árbol de recurrencia

Estaba resolviendo relaciones de recurrencia. La primera relación de recurrencia fue

$T(n)=2T(n/2)+n$

La solución de este puede ser encontrada por Master Theorem o el método del árbol de recurrencia. El árbol de recurrencia sería algo como esto:

La solución sería:

$T(n)=\underbrace{n+n+n+...+n}_{\log_2{n}=k \text{ times}}=\Theta(n \log{n})$

Luego me enfrenté al siguiente problema:

$T(n)=2T(n/2)+\log{n}$

Mi libro muestra que por el teorema maestro o incluso por algún enfoque de sustitución, esta recurrencia tiene la solución $\Theta(n)$. Tiene la misma estructura que el árbol anterior con la única diferencia que realiza en cada llamada$\log{n}$trabajo. Sin embargo, no puedo usar el mismo enfoque anterior para este problema.

El término no recursivo de la relación de recurrencia es el trabajo para fusionar soluciones de subproblemas. El nivel$k$ de su árbol de recurrencia (binario) contiene $2^k$ subproblemas con tamaño $\frac {n}{2^k}$, así que primero necesitas encontrar el trabajo total en el nivel $k$ y luego resumir este trabajo en todos los niveles de los árboles.

Por ejemplo, si el trabajo es constante $C$, entonces el trabajo total en el nivel $k$ estarán $2^k \cdot C$y el tiempo total $T(n)$ se dará por la siguiente suma:

$$T(n) = \sum_{k=1}^{\log_2{n}}2^k C = C(2^{\log_2{n}+1}-2) = \Theta(n)$$

Sin embargo, si el trabajo crece logarítmicamente con el tamaño del problema, deberá calcular con precisión la solución. La serie sería la siguiente:

$$T(n)=\log_2{n}+\underbrace{2\log_2(\frac {n} {2})+4\log_2(\frac {n} {4})+8\log_2(\frac {n} {8}) + ....}_{\log_2{n} \text{ times}}$$

Será una suma bastante compleja:

$$T(n)=\log_2{n}+\sum_{k=1}^{\log_2{n}}2^k \log_2(\frac {n} {2^k})$$

Voy a denotar temporalmente $m=\log_2{n}$ y simplifica la suma anterior:

$$\sum_{k=1}^{m}2^k \log_2(\frac {n} {2^k})=\\=\sum_{k=1}^{m}2^k(\log_2{n}-k)=\\=\log_2{n}\sum_{k=1}^{m}2^k-\sum_{k=1}^{m}k2^k=\\=\log_2{n}(2^{m+1}-2)-(m2^{m+1}-2^{m+1}+2)$$

Aquí usé una fórmula para el $\sum_{k=1}^{m}k2^k$suma de la calculadora de álgebra simbólica en línea Wolfram | Alpha . Entonces necesitamos reemplazar$m$ de vuelta por $\log_2{n}$:

$$T(n)=\log_2{n}+2n\log_2{n}-2\log_2{n}-2n\log_2{n}+2n-2$$ $$=2n-\log_2{n}-2=\Theta(n)$$

QED