algorithm - 用主定理求解递推关系

Question

我在这里感到困惑，主定理的哪种情况为这种递归关系找到了紧密的界限：

T(n) = 27T(n/3) + Q(n ³ log n)

这是我的解决方案：
f(n) = n ³ log n
a=27 b = 3 所以

所以我们可以在这里看到f(n) > n ³
所以这个：

案例 3 将适用：如果我在这里错了，请纠正我。
注意：但它的答案是 n ³ log ² n，这是由 Master Theorem 的案例 2 来的。我应该申请哪一个？

Answer 1

检查这个：

http://en.wikipedia.org/wiki/Master_theorem#Case_2

如果你有第三版 CLRS：参考问题 4.6-3

您应该能够根据主定理的证明推导出这一点，然后代入 f(n) 的形式。