解決類似復發：T（N）= 3T（N/3）+ N/3

鑑於..解決類似復發：T（N）= 3T（N/3）+ N/3

T(0) = 3 for n <= 1 

T(n) = 3T(n/3) + n/3 for n > 1

所以答案的假設是O(nlogn) ..以下是我做到了，這不是給我正確的答案：

T(n) = 3T(n/3) + n/3 

T(n/3) = 3T(n/3^2) + n/3^2

底塗此爲T（N）給出..

T(n) = 3(3T(n/3^2) + n/3^2) + n/3 

T(n/3^2) = 3(3(3T(n/3^3) + n/3^3) + n/3^2) + n/3

它最終會像..

T(n) = 3^k (T(n/3^k)) + cn/3^k

設置k = lgn..

T(n) = 3^lgn * (T(n/3^lgn)) + cn/3^lgn 

T(n) = n * T(0) + c 

T(n) = 3n + c

答案的O(n) though..What不對我的步驟是什麼？

來源

2014-04-24 user3567126

你應該申請碩士定理：http://en.wikipedia.org/wiki/Master_theorem – carl

T(n) = 3T(n/3) + n/3 
T(n/3) = 3T(n/9) + n/9 

T(n) = 3(3T(n/9) + n/9) + n/3 
    = 9T(n/9) + 2*n/3  //statement 1 

T(n/9)= 3T(n/27) + n/27 
T(n) = 9 (3T(n/27)+n/27) + 2*n/3 // replacing T(n/9) in statement 1 
     = 27 T (n/27) + 3*(n/3) 

T(n) = 3^k* T(n/3^k) + k* (n/3) // eventually

代替k，其中日誌n向基座3

T(n) = n T(1) + (log n) (n/3); 
// T(1) = 3 
T(n) = 3*n + (log n) (n/3); 
Hence , O (n* logn)

來源

2014-04-24 04:27:51 BlAcKBirD

哦，我的利空出現。非常感謝！ – user3567126

它最終會像.. T(n) = 3^k (T(n/3^k)) + cn/3^k

號最終，它會像

T(n) = 3^k * T(n/3^k) + k*n/3

你開不準確的括號。

來源

2014-04-24 04:27:17 user58697

這些類型的問題很容易使用masters theorem解決。在你的情況下，a = b = 3,c = log3(3) = 1，因爲n^c與f(n) = n/3的增長速度相同，所以屬於第二種情況。

這裏，你有你的k=1，因此答案是O(n log(n))

來源

2015-12-16 23:58:54

解決類似復發：T（N）= 3T（N/3）+ N/3

回答

相關問題