2013-10-16 56 views
-1

我真的很感激,如果有人可以幫助我幾個問題,需要幫助的證明了這一點認識主定理

以下的每一個遞歸函數的定義,用主定理來確定其生長的漸近階(即Big-Tetha)。如果你認爲大師定理不適用於某個特定情況,那麼應該正確解釋原因。在這些情況下,您仍然可以爲運行時間提供一個合理的上限(即Big-O)嗎?請注意,基本情況都假定爲常量。

的(a)T(N)= T(N/2)+ 2^N

(B)T(N)= 4T(N/2)+(N^1.5) - 1

(C)T(N)= T(N/3)+ 100

(d)是T(N)= 125T(N/5)+ N^3/LOGN

(e)中T(n)= 2T(n/7)+ log n +√n

我剛剛在網上閱讀了一些關於此的東西,我無法獲得足夠的理解來回答這個問題。任何幫助將不勝感激,我正在努力學習測試,我沒有得到任何這樣的!

非常感謝!

+0

這是一個編程網站上的數學問題......? – SuperPrograman

回答

0

除(a)以外的所有項目都可以使用馬斯特定理。在情況(a)中,收費函數不是多項式,因此主定理不適用。但可以通過擴張解決它:

T(n) = 2^n + T(n/2) 
    = 2^n + 2^(n/2) + T(n/4) 
    = 2^n + 2^(n/2) + 2^(n/4) + T(n/8) 
    = ... 
    = O(2^n). 

結果是通過intepreting復發作爲二進制數的總和明顯:1 + 10 + 100 + 10000 +千萬< = 2 * 10000000。