解决重复问题
我试图使用递归树来解决给定的递归，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 的形式吗？
这是我的一个普遍疑问，我需要对此有一个深入的了解。
笔记： 函数 k 中任何必须为 Theta(n^k log^k (n)) 的函数都应该 >=1。在这种情况下 k 是 -1 所以主定理不会出现在图中
Am trying to solve the given recursion, using recursion tree, T(n) = 3T(n/3) + n/lg n.
In the first level (n/3)/(log(n/3)) + (n/3)/(log(n/3)) + (n/3)/(log(n/3)) = n/(log(n/3)).
In the second level it turns out to be n/(log(n/9)).
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.
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
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
确实，马斯特定理并不适用。
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(1 和 logn 之间的积分 1/x) = Theta(log log n)。
因此 T(n) = ng(n) = Theta(nlog logn.)
你猜对了。
It is true, the Master theorem does not apply.
T(n) = 3T(n/3) + n/logn.
Let g(n) = T(n)/n.
Then ng(n) = 3(n/3)*g(n/3) + n/logn.
Thus
g(n) = g(n/3) + 1/log n.
This gives 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).
Thus T(n) = ng(n) = Theta(nlog logn.)
You guessed it right.
如果您使用树来可视化问题，您将看到每个排名的总和为：
（等于 n/log(n)）
- 排名 1：
等等，总和为
n/log(n/ (3^i))对于每个排名，i 是当前排名。所以，我们一起得到：如果我们打开方程，我们得到：
（从末尾开始向后移动..首先当 i=log(base3)n 时然后返回），
因为 log base 不会不管θ如何，我们得到：
这是：
这是（以 sigma 为单位）：
这是一个调和级数，等于：
并且由于 ln 是以 e 为底的对数，并且对数基数在 theta 中并不重要，我们最终得到：
等于：
所以，它是 theta(n log log n)。
If you use a tree to visualize the question, you'll see that the sum of each rank is:
(which is equal to n/log(n))
- rank 1:
and so forth, with a general sum of
n/log(n/(3^i))for each rank, i being the current rank. so, all together we get:if we open the equation we get:
(starting from the end and going backwards.. first when i=log(base3)n and then going back)
since log base doesn't matter in theta, we get :
which is:
which is (in sigma):
which is a harmonic series, equal to:
and since ln is log with a base of e, and log bases don't matter in theta, we finally get:
which is equal to:
so, it's theta(n log log n).
当
n<=1时，T(n)=3T(⌊n3⌋)+2nlogn基本条件为 1按替换法：
答案第 1 页
回答第 2 页
T(n)=3T(⌊n3⌋)+2nlognwith base condition 1 whenn<=1By substitution method:
Answer page 1
Answer page 2
