解决递归式

Question

我正在尝试使用递归树解决给定的递归问题，T(n) = 3T(n/3) + n/lg n。

在第一层中，(n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3))。

在第二层中，结果为n/(log(n/9))。

我能否以n.loglogn的形式概括上述方程？

这是我普遍的疑惑，我需要对此有所了解。

注意： 任何函数如果要在该函数中成为Theta(n^k log^k (n))，则k应>=1。而在这种情况下，k为-1，因此主定理不适用。

- Chaitanya

---

你是在寻找（闭式）解决方案，还是想要找到计算复杂度？ - BlueRaja - Danny Pflughoeft

Answer 1

确实，主定理不适用于此问题。

T(n) = 3T(n/3) + n/logn。

令g(n) = T(n)/n。

则ng(n) = 3(n/3)*g(n/3) + n/logn。

因此

g(n) = g(n/3) + 1/log n。

这给出了g(n) = Sum 1/log n + 1/log n/3 + 1/log n/9 + ...

= Theta(Sum 1/logn + 1/(logn -1) + 1/(log n - 2) + ...) = Theta(Integral 1/x between 1 and logn) = Theta(log log n)。

因此T(n) = ng(n) = Theta(nlog logn.)

你猜对了。

- Aryabhatta

---

似乎在引入g(n)=T(n)/n和n*g(n)=...部分之间的步骤中出现了错误；n/logn从未增加到n^2/logn。 - Adam Miller

我在微积分方面有些薄弱，你能否解释一下你是如何从Sum 1/logn + 1/(logn-1) + 1/(logn-2) + ... 推导到 Integral 1/x 在 1 到 logn 之间的过程？我可以理解你将无限极限和重写为积分，但我不明白具体是怎么做的。 - logdev

Answer 2

如果您使用树来可视化问题，您会看到每个级别的总和为：

- 级别0：

n/log(n)

- 级别1：

n/log(n/3)

等等，每个级别的一般总和为 n/log(n/(3^i))，其中 i 是当前级别。因此，我们得到：

如果我们打开方程式，我们得到：

(starting from the end and going backwards.. first when i=log(base3)n and then going back)

由于对数基数在 theta 中无关紧要，我们得到：

这是：

这是（用 sigma 表示）：

这是一个谐波级数，等于：

最后，由于 ln 是以 e 为底数的对数，而对数基数在 theta 中无关紧要，我们得到：

所以，它是 theta(n log log n)。

- shuminizer

---

我在打开链接之前就已经修复了它们，现在有点后悔:P。只需将数学放入 代码片段 中 - 这样更易读。 - Dan Scally

对于任何想了解谐和级数如何近似为log n的人，请查看此链接：https://math.stackexchange.com/questions/496116/is-there-a-partial-sum-formula-for-the-harmonic-series - logdev

Answer 3

T(n)=3T(⌊n/3⌋)+2nlogn，当n<=1时，为基本情况。

通过代入法：

答案第一页

答案第二页

- Kartik Khanna