recursion - Big-Oh 表示法的二次方程

Question

我正在审查有关 Big-Oh 运行时的中期测试。我遇到困难的问题之一是以下重复出现，问题是要求使用 Big-Oh 符号。

T(n) = 2T(n/2) + (2n^2 + 3n + 5)

因此，通过使用主定理，其中 k > log_b (a)，在这个问题中，我认为k是来自 (2n^2) 的 2，a是来自 2T 的 2，b是来自 (n/2) 的 2。因此，Master Theorem 的运行时间为 k > log_b (a)，即 2 > log_2 (2) = 1，则 T(n) = O(n^2)。

我的想法正确吗？我从未在 T(n) 中看到过二次运行时，但我相当确定在这个问题中它是 O(n^2)。

谢谢您的意见！

标签： recursionruntimebig-orecurrence

Answer 1

是的，O(n^2) 是正确的。实际上在维基百科关于主定理的文章中有一个类似的例子。这个函数可以是任何东西，基本上你只需将递归树的深度和宽度与这个附加函数的成本进行比较，然后检查是什么决定了复杂性。