algorithm - 递归关系 : T(n) = 2T(n/2) + log(n)

Question

我有一个递归关系，如下所示:

T(n) = 2T(n/2) + log₂ n

我正在使用递归树方法来解决这个问题。最后，我得出了以下等式:

T(n)=(2log₂n)(n-1)-(1*2 + 2*2² + ... + k*2 ^k) 其中 k=log₂n。

我正在尝试为这个方程找到一个 theta 符号。但是我找不到求和的封闭公式 (1*2 + 2*2² + ... + k*2^k)。我如何找到 T(n) 的大 theta 表示法？

Answer 1

如果您了解一些微积分，您应该能够轻松解决这个问题。

1 + x + x^2 + ... + x^(n+1) = (x^(n+2) - 1)/(x - 1)

乘以x， x + x^2 + x^3 + ... + x^(n + 2) = (x^(n + 3) - x)/(x - 1)

微分 LHS 将得到 x = 2 的级数。微分 RHS 将得到封闭形式。