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

希望这对您有所帮助!