使用主定理求解 T (n) = √2*T(n/2) + log n
Solving T (n) = √2*T(n/2) + log n using master theorem
问题是：
T(n) = √2*T(n/2) + log n
我不确定主定理在这里是否有效，有点卡住了。
根据主定理，f(n) 应该是多项式，但这里
f(n) = logn
这不是多项式，所以不能按照规则用主定理求解。我也在某处读到有关第四种情况的信息。我也必须提到这一点。
这里也讨论一下：
Master's theorem with f(n)=log n
但是，主定理有一个限制"fourth case"，这使得它可以应用于多对数函数。
如果
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
这看起来更像是 Akra-Bazzi 定理：http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method#The_formula 和 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).
Master theorem 仅对您的 a 和 b 有限制，这适用于您的情况。 a 是不合理的，而你有 log(n) 因为你的 f(n) 与它无关。
所以在你的情况下你 c = log2(sqrt(2)) = 1/2。由于 n^c 比你的 log(n) 增长得更快，递归的复杂度是 O(sqrt(n)).
P.S. Danyal 的解决方案是错误的，因为复杂度不是 nlogn 而 Edward Doolittle 的解决方案是正确的，在这种简单的情况下也是一种矫枉过正.
问题是：
T(n) = √2*T(n/2) + log n
我不确定主定理在这里是否有效，有点卡住了。
根据主定理，f(n) 应该是多项式，但这里
f(n) = logn
这不是多项式，所以不能按照规则用主定理求解。我也在某处读到有关第四种情况的信息。我也必须提到这一点。
这里也讨论一下： Master's theorem with f(n)=log n
但是，主定理有一个限制"fourth case"，这使得它可以应用于多对数函数。
如果
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
这看起来更像是 Akra-Bazzi 定理：http://en.wikipedia.org/wiki/Akra%E2%80%93Bazzi_method#The_formula 和 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).
Master theorem 仅对您的 a 和 b 有限制，这适用于您的情况。 a 是不合理的，而你有 log(n) 因为你的 f(n) 与它无关。
所以在你的情况下你 c = log2(sqrt(2)) = 1/2。由于 n^c 比你的 log(n) 增长得更快，递归的复杂度是 O(sqrt(n)).
P.S. Danyal 的解决方案是错误的，因为复杂度不是 nlogn 而 Edward Doolittle 的解决方案是正确的，在这种简单的情况下也是一种矫枉过正.