algorithm - 使用主定理求解 T (n) = √2*T(n/2) + log n

Question

问题是:

T(n) = √2*T(n/2) + log n

我不确定主定理在这里是否有效，有点卡住了。

Answer 1

这看起来更像是 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).