解決具有多個遞歸步驟的遞推方程

我在看一些算法，並且試圖確定在形成方程時如何處理多個遞歸步驟。解決具有多個遞歸步驟的遞推方程

所以表現出： Exhibit A

很明顯，我認爲這裏的遞推方程是：T（N）= C + 2T（N/2），其在大O符號簡化爲爲O（n ）

但是在這裏， Exhibit B 我們也有類似的情況發生，我得到了遞推方程T（n）= n + 2T（n/2），因爲我們有兩個遞歸調用與第一個調用不同，大O符號簡化爲O（n），然而在這裏情況並非如此。任何關於如何在這第二個在這裏得到正確的遞推方程的輸入？

任何關於如何去解決這個問題的意見都會很棒。

來源

2012-12-21 Louis93

這晚，我可能讀錯了，但你不小心發佈相同的代碼片斷兩次？ –

你發佈的兩個功能都一樣，是你的意圖嗎？ –

不，但你們是對的！我很抱歉，我只是修復它。沒注意到我自己。 – Louis93

你可能會感興趣的主定理：

http://en.wikipedia.org/wiki/Master_theorem

遞推方程T(n) = n + 2T(n/2)是Theta(n log n)，可使用定理推導。做手工，你也可以承擔n = 2^k做：

T(n) = 2T(n/2) + n 
    = 2(2T(n/4) + n/2) + n 
    = (2^2)T(n/(2^2)) + 2n 
    = (2^2)(2T(n/(2^3)) + n/(2^2)) + 2n 
    = (2^3)T(n/(2^3)) + 3n 
    = ... 
    = (2^k)T(n/(2^k)) + kn 
    = nT(1) + n log2 n 
    = Theta(n log n)

來源

2012-12-21 03:37:31

斯圖爾特你介意再看看這個問題嗎？我用固定圖像鏈接更新了它 – Louis93

解決具有多個遞歸步驟的遞推方程

回答

相關問題