algorithm - 递归关系：T (n/16) + n log n

Question

可以应用主定理吗？

或者说 for T (n) = 2T (n/16) + n log n，这里如何应用主定理？

我得到了a = 2，b = 16我不确定cand k。

Answer 1

要解决这样的递推关系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))

有关更多详细信息，请参阅大师定理。

因此，在您的情况下：a = 2, b = 16⇒适用于情况 3， 因此在.e = log16(2) = 0.25
T(n)Θ(n log n)

Answer 2

即使 log (n) 项不存在，每个级别上每个子问题的工作量也占主导地位 (b > a)。因此，在我看来，复杂性应取决于在最高级别完成的工作，即 O (nlogn)。