復發：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)，因此小於二次方。