複製關係：T（n/16）+ n log n

Question

主定理可以應用嗎？

或者說對於T (n) = 2T (n/16) + n log n，主法則在這裏如何應用？

我得到a = 2,b = 16，我不確定c和k。

Answer 1

即使log（n）項不存在，每個級別的每個子問題的工作量減少佔主導地位（b> a）。因此，我認爲複雜性應該由在最高層次上完成的工作決定，即O（nlogn）。

Answer 2

要解決這種復發關係T(n) = a⋅T(n/b) + f(n)，您必須計算e = logb(a)。

然後（對於ε > 0）：

1. f(n) ∈ O(ne - ε)⇒T(n) ∈ Θ(ne)
2. f(n) ∈ Θ(ne)⇒T(n) ∈ Θ(ne⋅log(n))
3. f(n) ∈ Ω(ne + ε)⇒T(n) ∈ Θ(f(n))

詳情參見Masters Theorem。

所以你的情況：a = 2，b = 16⇒e = log16(2) = 0.25適用於情況3，
所以T(n)是Θ(n log n)。