的復發T（N）= 2T（N/2）+（N-1）

我有此復發：的復發T（N）= 2T（N/2）+（N-1）

T(n)= 2T(n/2) + (n-1)

我嘗試是如下：

樹是這樣的：

T(n) = 2T(n/2) + (n-1) 
T(n/2) = 2T(n/4) + ((n/2)-1) 
T(n/4) = 2T(n/8) + ((n/4)-1) 
...

樹的高度：（N /（2 ^ħ）） - 1 = 1⇒H = LG N - 1 = LG N - LG 2
的最後一級的成本：2 ^ħ = 2 ^{LG N - LG 2} =（1/2）N
各級直到水位h-1的成本：Σ_{I = 0，.. 。，LG（2N）} N - （2 ^我 -1），這是一個幾何級數和equals（1/2）（（1/2）N-1）

因此，T（ n）=Θ（n lg n）

我的問題是：是嗎？

來源

2011-11-29 Sosy

不，它不是。你的最後一級的成本是錯誤的，所以你從中得出的結論也是錯誤的。

（我假設你想找到自己的複雜性，所以沒有更多的提示，除非你問。）

編輯：一些提示，根據要求

要查找的複雜性，人們通常有幫助的方法是遞歸應用的方程和結果插入第一，

T(n) = 2*T(n/2) + (n-1) 
    = 2*(2*T(n/4) + (n/2-1)) + (n-1) 
    = 4*T(n/4) + (n-2) + (n-1) 
    = 4*T(n/4) + 2*n - 3 
    = 4*(2*T(n/8) + (n/4-1)) + 2*n - 3 
    = ...

，往往導致一個封閉的公式，你可以通過感應證明（你不需要，如果你有足夠的經驗來進行證明，那麼你s ee沒有寫下證明的正確性）。

劇透：你可以在幾乎任何處理主定理的資源中查找複雜性。

來源

2011-11-29 19:35:57

好吧，我可以使用一些提示：D，是對的嗎？ – Sosy

@Sosy是的，高度是正確的。 –

最後一級的成本=節點數* T（1） = 2^h其中h = lg2n ..我不知道錯在哪裏：S – Sosy

這可以通過Masters theorem輕鬆解決。

您有a=2,b=2,f(n) = n - 1 = O(n)因此c = log2(2) = 1。這是師父定理的第一種情況，這意味着複雜度爲O(n^c) = O(n)

來源

2015-12-14 00:26:30

的復發T（N）= 2T（N/2）+（N-1）

回答

相關問題