math - 当存在三个术语时应用主定理？

Question

我将如何使用主定理解决这种递归？

T(n) = 4T(n/2) + n ² + logn

我不知道该怎么做，但我很确定可以使用 Master Theorem 解决它。我必须忽略其中一个条款吗？任何帮助表示赞赏，谢谢。

Answer 1

主定理适用于可以写成的函数

T(n) = aT(n / b) + f(n)

在这里，您有 a = 4、b = 2 和 f(n) = n ² + log n。请注意，我们将“n ² + log n”组合在一起作为 f(n) 项，而不是将其视为两个单独的项。

现在我们已经完成了，我们可以直接应用主定理。请注意，log _b a = log ₂ 4 = 2 并且 f(n) = Θ(n ² )，因此根据主定理，这求解为 Θ(n ² log n)。之所以可行，是因为 n ² + log n = Θ(n ² )，而主定理只关心 f(n) 的渐近复杂度。事实上，任何这些重复都可以用相同的方式解决：

T(n) = 4T(n / 2) + n ² + 137n + 42

T(n) = 4T(n / 2) + 5n ² + 42n log n + 42n + 5 log n + 10 ⁶

T(n) = 4T(n / 2) + 0.5n ² + n log ¹³⁷ n + n log n + n ² / log n + 5

希望这可以帮助！