復發：T（n）= T（n/2）+ log N

Question

我被困在一個復發問題上。

T（N）= T（N/2）+日誌N

我現在所擁有的是：

T（N）= T（N/2）+日誌N

T（N/2）= T（N/4）+日誌（N/2）

...

T（N）= T（N/2^k）的總和+ [I = 0和k {log（N/2^i）}]

我被困在接下來要做的事情上。請給我一些建議。

謝謝！

Answer 1

終止條件未在數學方程中給出，所以如果您藉助修改後的母版定理版本解決此問題會更好。我在這裏提供了這些問題的鏈接，請看看這個問題，可能你會得到你正在尋找的東西。 請看第二個答案。

here

Answer 2

T(1) = c       (= c + 0) 
T(2) = T(1) + log(2)    = c + 1 
T(4) = T(2) + log(4) = c + 1 + 2 = c + 3 
T(8) = T(4) + log(8) = c + 3 + 3 = c + 6 
T(16) = T(8) + log(16) = c + 6 + 4 = c + 10 
... 

n | T(n) | T(n) - T(n-1) 
--+--------------------- 
1| c + 0| - 
2| c + 1| 1 
4| c + 3| 2 
8| c + 6| 3 
16| c + 10| 4 

T(n) = c + (log n)(1 + log n)/2 = O(log^2 n) 

另一種方式看到同樣的事情：

n = 2^m 
S(m) = T(2^m) = T(2^m/2) + log(2^m) = S(m - 1) + m 
m | S(m) 
--+----- 
0 | c 
1 | c + 1 
2 | c + 1 + 2 = c + 3 
3 | c + 3 + 3 = c + 6 
4 | c + 6 + 4 = c + 10 
... 
S(m) = c + m(m + 1)/2 
T(2^m) = c + m(m + 1)/2 
T(n) = c + (log n)(1 + log n)/2 = O(log^2 n) 

Answer 3

另一種方法是使用Master Theorem（或Wikipedia）。對於大多數復發來說，它是適用的並且提供非常快的答案。

它基本上給你三個類別，然後答案掉了。給定形式T（n）= aT（n/b）+ f（n）的重現，我們尋找a，b和f（n）。在你的情況下，我們有a = 1，b = 2，f（n）= log n。 （n）（log_b（a-eps））log^k（n））= Theta（（））（）（）（）（）（） （n）），那麼主定理指出T（n）在Theta（n ^（log_b（a-eps））log ^（k + 1）（n））= Theta（log^2 （n））