解决递归式：T(n)=2T(n/2)+n/logn。

Question

我可以找到每一行的总和(n/log n-i)，也可以画出它的递归树，但我无法计算每一行的总和。

T(n)=2T(n/2)+n/logn

T(1) = 1

- Saeedeh

Answer 1

假设 n = 2^k；

对于调和级数（欧拉公式）我们知道：

Sum[i = 1 to n](1/i) ~= log(n) [n -> infinity]

t(n) = 2t(n/2) + n/log(n)
     = 2(2t(n/4) + n/2/log(n/2)) + n/log(n)
     = 4t(n/4) + n/log(n/2) + n/log(n)
     = 4(2t(n/8) + n/4/log(n/4)) + n/log(n/2) + n/log(n)
     = 8t(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
     = 16t(n/16) + n/log(n/8) + n/log(n/4) + n/log(n/2) + n/log(n)
     = n * t(1) + n/log(2) + n/log(4) + ... + n/log(n/2) + n/log(n)
     = n(1 + Sum[i = 1 to log(n)](1/log(2^i)))
     = n(1 + Sum[i = 1 to log(n)](1/i))
     ~= n(1 + log(log(n)))
     = n + n*log(log(n)))
     ~= n*log(log(n)) [n -> infinity]

- Danil Speransky

Answer 2

当您开始展开递归时，您将得到以下结果：

你的基本情况是 T(1) = 1，这意味着 n = 2^k。代入后得到：

第二个求和式的行为与调和级数相同，因此可以近似为log(k)。现在k = log(n)，得出的答案是：

- Salvador Dali

---

抱歉在这篇旧帖子中提问，但我一直在寻找您的答案，并一直试图理解为什么从i = 0到k-1 {1 /（k-i）}的总和与调和级数的行为相同。先行致谢。 - Martian

请将这个式子直接写成k-1个元素的求和形式，这样很明显就能看出来了。 - Salvador Dali

Answer 3

按照下面的扩展主定理进行操作。

使用扩展主定理T(n)=2T(n/2)+n/logn可以轻松解决，具体如下。 这里n/logn部分可以重写为n * (logn)^-1，有效地使得p=-1。 现在可以轻松应用扩展主定理，它将与扩展主定理的第2b种情况有关。

T(n)= O(nloglogn)

请跟随以下内容获取更详细的解释

https://www.youtube.com/watch?v=Aude2ZqQjUI

- Tapan