复发：T（n）=（2 + 1/log n）T（n/2）

Question

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

T（N）=（2 + 1/log n）的T（N/2）

Answer 1

经过一些想法我不能想出一个精确解。师父的定理在这里不起作用，展开树没有给我任何合理的东西。所以我只是用以下方式来估计复杂性。

对于任何合理的大n你可以估计0 < 1/log n < 1。所以你可以得到：

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

and O(T1) < O(T) < O(T2)。您可以使用master theorem找到两次重复的复杂性。 T1的复杂度为O(n)，而T2的复杂度为O(n^log2(3))。

因此，您可以确定您的复发复杂度大于O(n)且小于O(n^1.58)，因此小于二次方。