当有三个项时应用主定理？

Question

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

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

我不知道如何去做，但我很确定可以使用主定理来解决它。我是否必须忽略其中一项条款？任何帮助表示赞赏，谢谢。

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

希望这可以帮助！