我试图解决给定的递归，使用递归树，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 所以主定理不会出现在图片中
确实，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 和 logn 之间的积分 1/x) = Theta(log log n)。
因此 T(n) = n g(n) = Theta(n log logn.)
你猜对了。
如果您使用树来可视化问题，您会看到每个等级的总和为：
（等于 n/log(n)） - 等级 1：
依此类推，n/log(n/(3^i))每个等级的总和，i 是当前等级。所以，我们一起得到：
如果我们打开方程，我们得到：
（从头开始并向后走..首先当 i=log(base3)n 然后返回）
由于对数基数在 theta 中无关紧要，我们得到：
这是：
这是（在西格玛）：
这是一个谐波级数，等于：
由于 ln 是以 e 为底的对数，而对数底在 theta 中无关紧要，我们最终得到：
这等于：
所以，它是theta（n log log n）。
T(n)=3T(⌊n3⌋)+2nlognn<=1
当通过替换方法时，基本条件为 1 ：
回答第 1 页
回答第 2 页
