问题是 ：
T(n) = √2*T(n/2) + log n
我不确定主定理是否在这里有效，并且有点卡住了。
问问题
4684 次
3 回答
3
这看起来更像 Akra-Bazzi 定理：http ://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method#The_formula with k=1, h=0, g(n)=log n, a=(2)^{1/2}, b=1/2。在这种情况下，p=1/2您需要评估积分\int_1^x log(u)/u^{3/2} du。您可以使用按部分积分或符号积分器。Wolfram Alpha 告诉我不定积分是-2(log u + 2)/u^{1/2} + C，所以定积分是4 - 2(log x + 2)/x^{1/2}。加上1并乘以x^{1/2}，我们得到T(x) = \Theta(5x^{1/2} - 2 log x - 4)。
于 2015-05-04T22:07:06.817 回答
1
根据主定理，f(n) 应该是多项式，但在这里
f(n) = logn
这不是多项式，因此不能按照规则由主定理解决。我也在某处读到了第四个案例。我也必须提到这一点。
这里也讨论了： Master's theorem with f(n)=log n
然而，主定理有一个有限的“第四种情况”，它允许它应用于多对数函数。
如果
f(n) = O(nlogba logk n), then T(n) = O(nlogba log k+1 n).
换句话说，假设你有 T(n) = 2T (n/2) + n log n。f(n) 不是多项式，而是 f(n)=n log n，并且 k = 1。因此，T(n) = O(n log2 n)
有关更多信息，请参阅此讲义：http: //cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-HandoutNoNotes.pdf
于 2015-05-04T20:39:00.767 回答
1
主定理仅对您有约束，a并且b适用于您的情况。a这是非理性的事实，log(n)你拥有的f(n)与它无关。
所以在你的情况下，你的c = log2(sqrt(2)) = 1/2. 由于n^c增长速度比您的 log(n) 快，因此递归的复杂度为O(sqrt(n)).
Danyal 的PS解决方案是错误的，因为复杂性不是 nlogn，而 Edward Doolittle 的解决方案是正确的，在这种简单的情况下也是一种矫枉过正。
于 2015-12-17T07:15:28.980 回答