algorithm - 重复:T(n) = (2+1/log n)T(n/2)

Question

我必须用树的方法来解决这个递归关系，因为主定理不适用。

T(n) = (2+1/log n) T(n/2)

Answer 1

经过一番思考，我想不出一个确切的解决方案。大师的定理在这里不起作用，伸展树(Splay Tree)没有给我任何合理的东西。所以我将按以下方式估算复杂性。

对于任何相当大的 n你可以估价0 < 1/log n < 1 .所以你可以得到:

T1(n) = 2 * T1(n/2)
T2(n) = 3 * T2(n/2)

和O(T1) < O(T) < O(T2) .您可以使用 master theorem 找到两次重复的复杂性. T1的复杂性是O(n)和 T2是O(n^log2(3)) .

所以你可以确定你的递归复杂度大于O(n)小于O(n^1.58) , 所以小于二次。