解决复发 [英] Solving recurrences

问题描述

我试图给定的递归来解决，用递归树， T（N）= 3T（N / 3）+ N / LGñ。

Am trying to solve the given recursion, using recursion tree, T(n) = 3T(n/3) + n/lg n.

在第一级（N / 3）/（日志（N / 3））+（N / 3）/（日志（N / 3））+（N / 3）/（的log（n / 3））= N /（日志（N / 3））。

在二级它原来是 N /（日志（N / 9））。

我可以概括上述公式中的形式 n.loglogn

Can I generalize the above equation in the form of n.loglogn

这是一个普遍的疑问我有，我需要一个这样的见解。

This is a general doubt I've, I need an insight on this.

请注意： 有任何功能为的Theta（N ^ķ日志^ K（N））在函数K应该> = 1。在这种情况下k为-1所以主定理不进来图片

Note: Any function that has to be Theta(n^k log^k (n)) in that function k should >=1. And in this case k is -1 so master theorem doesn't come in to picture

推荐答案

这是事实，法师定理并不适用。

It is true, the Master theorem does not apply.

T（N）= 3T（N / 3）+ N / LOGN。

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

让G（N）= T（N）/ N。

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

则N * G（N）= 3 *（N / 3）* G（N / 3）+ N / LOGN。

Then n*g(n) = 3*(n/3)*g(n/3) + n/logn.

于是

G（N）= G（N / 3）+ 1 /日志ñ。

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

这使G（N）= SUM 1 /日志N + 1 /日志N / 3 + 1 /日志N / 9 + ...

This gives g(n) = Sum 1/log n + 1/log n/3 + 1/log n/9 + ...

=西塔（总和1 / LOGN + 1 /（LOGN -1）+ 1 /（日志N - 2）+ ...）=西塔（积分1 / X 1至LOGN）=西塔（日志日志N ）。

= 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）= N * G（N）=西塔（N *登录LOGN）

Thus T(n) = n*g(n) = Theta(n*log logn.)

您猜对。

这篇关于解决复发的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！