algorithm - 涉及大 O 表示法的递归关系

Question

递归关系 T(n) = 2T(n/2) + O(n^2) 的解被给出为 n^2 的 Big theta。

我们如何得到这个解决方案。

我解决它的方式：- 递归树的高度是 logn。我们在每一步都有 n^2 复杂度。所以递归关系是O（n ^ 2 logn）。

在这种情况下，我们如何在 Big theta 中得到答案？

Answer 1

你可以参考“主定理”。

您的问题属于定理的第 3种情况，因此根据其结论，复杂度为Θ(n^2).