Necesita ayuda para resolver una relación de recurrencia

Question

Tengo una relación de recurrencia, que es como el siguiente:

$$ T(n) = 2T(n/2) + \log_2 n. $$

Estoy usando recursividad método de árbol para resolver esto. Y al final, se me ocurrió la siguiente ecuación:

$$ T(n)=(2\log_2 n)(n-1)-(1*2 + 2*2^2 + \ldots + k*2^k) $$ donde $k=\log_2 n$.

Estoy tratando de encontrar una notación theta para esta ecuación. Pero no puedo encontrar un cerrado fórmula para la suma $$ 1*2 + 2*2^2 + \ldots + k*2^k.$$

¿Cómo puedo encontrar un gran notación theta para $T(n)$?

Gracias.

Answer 1

Como se observa en la Marvis, la secuencia de $x_m=T(2^m)$ cumple el primer orden lineal de la recurrencia de la fórmula $$ x_m=2x_{m-1}+m. $$ La ecuación homogénea $x_m=2x_{m-1}$ tiene solución general $x_m=C2^m$. Esto puede comprobarse mediante la inducción, sino que se deduce fácilmente a partir de la teoría general de recurrencia lineal homogénea de las secuencias.

Desde que la no homogénea parte es un grado $1$ polinomio, buscamos una solución particular de la forma $x_m=Am+B$. Esto se llama el método de coeficientes indeterminados. Conectar esta es la fórmula de los rendimientos $$ Am+B=2 a(m-1)+B)+m. $$ Así que tenemos una solución si tomamos $A=-1$$B=-2$. Es decir,$x_m=-m-2$.

Finalmente, la solución general es la suma de la general de la solución homogénea y la solución particular, a saber,$x_m=C2^m-m-2$. Haciendo $m=0$ rendimientos $x_0=C-2$, por lo que $$ x_m=(x_0+2)2^m-m-2. $$

Volviendo a $T(n)$, esto puede ser expresado como $$ T(n)=(T(1)+2)n-\log_2n -2 $$ para todos los poderes de $2$.

Answer 2

Deje $T(0)=0$ y dejar que la recurrencia de la relación ser $$ T(n) = 2 T(n/2) + \lfloor \log_2 n \rfloor.$$

Además vamos a la representación binaria de $n$ ser $$ n = \sum_{k=0}^{\lfloor \log_2 n \rfloor} d_k 2^k.$$

Entonces no es difícil ver que $$ T(n) = \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j (\lfloor \log_2 n \rfloor-j) = \lfloor \log_2 n \rfloor \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j - \sum_{j=0}^{\lfloor \log_2 n \rfloor} 2^j j = 2^{\lfloor \log_2 n \rfloor+1} -\lfloor \log_2 n \rfloor - 2.$$ Esta fórmula tiene para todos los $n$ y no sólo potencias de dos.

Esta recurrencia es tan simple que no dependen de los valores de los bits que forman $n$, pero sólo en su número. Simplificando, obtenemos $$ T(n) = 2^{\lfloor \log_2 n \rfloor+1}-\lfloor \log_2 n \rfloor - 2 \in \Theta(n).$$

Este procedimiento es empleado en un poco de la forma más sofisticada en el siguiente enlace.