如何使用主定理來計算遞歸，分而治之

Question

我想計算Θ（）

Given T (n) = T (n − 1) + n^3 

我不能直接申請碩士定理規則，因爲我不知道什麼是B，所以如何導出Θ（）？

Answer 1

爲什麼你必須在這裏使用主定理？它可以直接解決這樣的：

T(n) = T(n-1) + n^3 
T(n-1) = T(n-2) + (n-1)^3 
T(n-2) = T(n-3) + (n-2)^3 
.   .  . 
.   .  . 
.   .  . 
T(1) = T(0) + 1^3 
----------------------- (Add them all and cancel) 

T(n) = T(0) + (n(n-1)/2)^2 (Sum of the cubes of the first n numbers) 

因此，這是O(n^4)

Answer 2

T(n) = T(n-1) + n^3 
    = T(n-2) + n^3 + (n-1)^3 
    = T(n-i+1) + (n-i)^3 + ... + (n-1)^3 + n^3 
    = 1^3 + 2^3 + ... + (n/2)^3 + (n/2+1)^3 + ... + (n-1)^3 
    Throw bottom half and decrease the half top to n/2 
    > ((n/2)^3)*(n/2) 
    Ω(n^4) 

    Increase all to (n-1) 
    = 1^3 + 2^3 + ... + (n/2)^3 + (n/2+1)^3 + ... + (n-1)^3 < (n-1)^3*n = O(n^4) 


    T(n) = θ(n^4)