解决复发问题

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,因此主定理不会进入图像

Answer 1

确实,Master定理不适用.

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

设g(n)= T(n)/ n.

然后n g(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(积分1/x在1和logn之间)= Theta(log log n).

因此T(n)= n g(n)= Theta(n log logn.)

你猜对了.

Answer 2

如果您使用树来可视化问题，您会看到每个排名的总和是：

• 等级 0：

（等于 n/log(n)） - 等级 1：

依此类推，n/log(n/(3^i))每个等级的总和为 ， i 是当前等级。所以，我们一起得到：

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

（从末尾开始向后移动..首先当 i=log(base3)n 时，然后返回）

由于 log base 在 theta 中无关紧要，我们得到：

即：

这是（在西格玛）：

这是一个调和级数，等于：

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

这等于：

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