計算遞推關係T（N）= N + T（N/2）

Question

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

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

= N + N/2 + N/4 + T（N/8）

= N + N/2 + N/4 + ... + N /（2 ^（K- 1））+ T（N/2^k）的

- >>>

，我不知道如何克o上得到大哦公式。 請幫我

Answer 1

我假設有一些初始條件，如T(1) = 0，你不告訴我們。

如果是這樣，答案是O(log n)。

想想你將如何制定出T(2)，T(4)，T(8)，T(16)等每個人只需要一個額外的步驟。

T(1) = T(2^0) calls the method recursively 0 times. 
T(2) = T(2^1) calls the method recursively 1 time 
T(4) = T(2^2) calls the method recursively 2 times 
T(8) = T(2^3) calls the method recursively 3 times 

換句話說，步數是功率。這意味着你必須取對數來得到答案。