algorithm - 如何解决下面的递归关系？

Question

这个问题是在考试中提出的，我不知道怎么做。有谁能帮我或给我一些提示。我认为师父的方法不适用于这里？
请帮忙。
T（n）=T（n/2）+θ（logn）

Answer 1

假设n是2的幂，比如说n = 2^k，为了简单起见，让我们假设T(n) = T(n/2) + lg(n)其中lg是对数基，并且2。

T(n) = lg(n) + lg(n/2) + lg(n/4) + ... + lg(1)
     = lg(2^k) + lg(2^{k-1}) + ... + lg(2^0)
     = k.lg(2) + (k-1)lg(2) + ... + 0.lg(2)
     = (k + (k-1) + ... + 0) lg(2)
     = k(k+1)/2
     = lg(n)(lg(n)+1)/2
     = Theta(lg(n)^2).

由于 T(1) = lg(1) = 0不是 n的幂，可以注意到 2是一个递增函数，因此 T在 T(2^k) <= T(n) <= T(2^{k+1})处。从上面的精确结果，我们得到

k(k+1)/2 <= T(n) <= (k+1)(k+2)/2

所以

T(n) = Theta(floor(lg(n))^2) = Theta(lg(n)^2)