問題詳情

34.若有一問題的時間複雜度T(n)滿足以下公式：T(n) = T(n/3) + T(2n/3) + O(n)，則T(n)等於下列何者？
(A)O(n log2n)
(B)O(n log n)
(C)O(n2log n)
(D)O(n2log2n)

參考答案

答案：B
難度：適中0.551402
統計：A(6),B(59),C(13),D(3),E(0)

用户評論

【BlancJamie】評論

【澐】評論

請教各位想法

【william】評論

T(n) = T(n/3) + T(2n/3) + O(n) = T(n)+ O(n) a  =1,b=1,d=1;套用主定理-Master-Theorem，得到d = logba 1 = log11 O(nlogn)參考：http://jonathenzc.github.io/2015/03/04/%E4%B8%BB%E5%AE%9A%E7%90%86-Master-Theorem/