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 将为您提供封闭形式。

Answer 2

根据我的计算，我想您犯了一些错误：

T(n)=(k-1)*log(n/(2^(k-1)))+2^k*T(n/2^k)。

把 k=log(n)

如果您愿意，我可以发布我的解决方案的图片。:)

Answer 3

你应该使用主定理来计算你的复杂性，它会容易得多。

Answer 4

这些递归可以用大师定理解决。在你的情况下a = 2，b = 2因此c = logb(a) = 1。

你的f(n) = log nand 因为n^c增长得比你的快f，所以它在解决方案中占主导地位，你属于第一种情况。所以复杂度是O(n)。