Estoy tratando de resolver una función recursiva:$$ T(n)= 2 T(n/2)+n \lg(n), \quad n>2,\quad T(2)=2,\quad n = 2^{k}$ $
El teorema maestro no funcionó. El resultado no tiene sentido (si lo hice bien).
¿Alguna sugerencia?
Respuestas
¿Demasiados anuncios?
Prefiero recurrir a trucos ad-hoc para resolver tales recursiones. Divida por$n$ para obtener: $$ \ frac {T (n)} {n} = \ frac {T (n / 2)} {(n / 2)} + \ lg n. $$ Suponiendo que$n$ es una potencia de$2$, es fácil ver que $$ \begin{eqnarray*} \frac{T(n)}{n} &=& \lg (n) + \lg \left( \frac{n}{2} \right) + \lg \left( \frac{n}{2^2} \right) + \cdots + \lg (1) \\ &=& \lg n + (\lg n - 1) + (\lg n -2) + \cdots + 0 \\ &=& \frac{1}{2} \lg n \cdot (\lg n +1) \\ &=& \Theta((\lg n)^2), \end {eqnarray *} $$ que implica$T(n) = \Theta(n (\lg n)^2)$.
Es convencional agitar la mano en este punto y murmurar algo sobre$n$, no una potencia de$2$ ...
sewo
Puntos
58
La recurrencia solo parece estar bien definida cuando$n$ es una potencia de$2$, así que permite$n=2^k$. Entonces podemos expandir la recurrencia hasta que lleguemos a T (2): $$ \begin{align}T(2^k) &= 2^kk + 2\cdot 2^{k-1}(k-1) + 2^2\cdot2^{k-2}(k-2) + \cdots + 2^{k-2}\cdot 2^2 2 + 2^{k-1}2 \\ &= 2^k \sum _{j=1}^{k} j = 2^k\frac{k(k+1)}{2} = 2^{k-1}k(k+1)\quad \mathrel{\Big[=} O(n\log^2(n))\Big]\end {align} $$
Mike
Puntos
1113
Mientras que un caso del teorema maestro fácilmente se aplica, éste también es bastante simple que puede resolverse a través de la inducción. Considerar $$ \begin{align}T(2^k) &= k2^k + 2T(2^{k-1})\ &= k2^k+2\bigl((k-1)2^{k-1}+2T(2^{k-2})\bigr) \ &= k2^k+(k-1)2^k+4T(2^{k-2}) \end{align} $$ etc; you should be able to continue this to find the value of $T(2^k) $, and then use that to prove that the asymptotic result holds for values of $n $ that aren't powers of $2$.
