解决复发

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

这是真的，主定理不适用。

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 /日志Ñ

这给出了G（N）= SUM 1 /日志N + 1 /日志N / 3 + 1 /日志N / 9 + ...

=西塔（萨姆1 / LOGN + 1 /（LOGN -1）+ 1 /（对数N - 2）+ ...）= THETA =西塔（积分1 / X 1和LOGN之间）（loglogN个）。

因此T（N）= N G（N）=西塔（N 日志LOGN。）

您猜测是正确的。

Answer 2

如果你使用一棵树可视化的问题，你会看到的总和每个排名是:

• 排名0:

(等于n/log(n)) -1级:

等等，有一大笔 n/log(n/(3^i)) 对于每一级，我正在目前的等级。因此，所有在一起我们会得到：

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

(从端和倒退..第一，当我=log(base3)n然后回去)

由于日志基础不论在theta，我们会得到：

这是：

这是(在sigma):

这是一个谐波系列，等于：

自ln日志与基的电子和记录基地，不论是在theta，我们终于获得：

这等于：

所以，这是θ(n登记录n)。