我必须用树的方法来解决这个递归关系，因为主定理不适用。
T(n) = (2+1/log n) T(n/2)
最佳答案
经过一番思考，我想不出一个确切的解决方案。大师的定理在这里不起作用，伸展树(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) , 所以小于二次。
关于algorithm - 重复:T(n) = (2+1/log n)T(n/2)，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/33585859/