复制关系：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)。