阿摩線上測驗
26. 當一個演算法可以遞迴關係式來進行表示的時候，我們有機會可以利 Master Theorem 來評估該演算法的時間複雜度。給定下面的時間函數，請利 Master Theorem 來評估時間複雜度: 
(A) Θ (n2)
(B) Θ(n3)
(C) Θ (n2 log n)
(D) Θ (n2 log2 n)
(A) Θ (n2)
(B) Θ(n3)
(C) Θ (n2 log n)
(D) Θ (n2 log2 n)
答案：登入後查看
統計： A(14), B(11), C(44), D(21), E(0) #2706368
統計： A(14), B(11), C(44), D(21), E(0) #2706368
詳解 (共 1 筆)
Snow Pining
#5757776
T(n) = aT(n/b)+f(n)
其中 a = 9, b = 3, f(n) = n2 log n
要使用主定理，我們需要比較 f(n) 和 n(logb a) 的大小關係。
在這個例子中，n(logb a) = n(log3 9) = n2。因此，我們得到：
f(n) = Θ(n(logb a) logk n)，其中 k = 1
主定理會探討三種情況，其詳細判斷方式可見 主定理的維基百科，此時符合主定理的第二種情況，根據該定理，我們可以得到：
T(n) = Θ(n(logb a) log(k+1) n)
此時將 a 代入9、b 代入3、k 代入1，我們得到：
T(n) = Θ(n2 log2 n)
這就是本題遞迴函式的時間複雜度。
0
0
