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

EN

这看起来更像Akra定理：公式 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告诉我，不定积分是-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)。

主定理只对您的a和b有限制，这对您的情况是成立的。事实上，a是非理性的，你有log(n)，因为你的f(n)和它无关。

所以在你的例子中，你的c = log2(sqrt(2)) = 1/2。由于n^c比日志(N)增长得更快，递归的复杂性是O(sqrt(n))。

Danyal的P.S.解是错误的，因为它的复杂性不是nlogn，爱德华杜立德的解是正确的，在这个简单的情况下也是过分的。

根据主定理，f(n)应该是多项式，但在这里

f(n) = logn

它不是多项式，因此不能按规则用主定理求解。我也在某个地方读过关于第四个案子的文章。我也必须提到这一点。

这里还将讨论：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 log2，k= 1。因此，T(n) = O(n Log2 N)

有关更多信息，请参见此讲义：http://cse.unl.edu/~choueiry/S06-235/files/MasterTheorem-HandoutNoNotes.pdf