algorithm - 计算最严格的 Big-Oh 循环边界

Question

在我的算法课上，我们正在学习递归，但我完全迷失了方向，不知道该怎么做。我从 Bowdoin 找到了这个 pdf Solving Recurrences with the Iteration/Recursion-tree它解释得更好一些，但提供的示例不包括 Big Oh。我有下面列出的问题之一。我们如何操作递归迭代树来合并 O(n^2)？如果有人能够解释在 Big Oh 涉及复发的情况下该怎么做，我将不胜感激。谢谢

T(n) = T(n−4)+O(n^2)

Answer 1

我想通过说明以下内容来跟进其他答案:

You cannot simply, in the general case, naively multiply the number of occurrences by the complexity of each individual occurrence.

安全的做法是精确地评估递归 - 即不使用 O 符号，并在末尾“重新应用”O 符号，仅采用前导项.

---

让我们看一下这个例子。定义一个函数 S(n)计算精确系列值:

假设递归在 n <= 0 时停止, 然后有 floor(n / 4)扩展系列中的术语:

在步骤 (*) 中我们使用了 standard formulae求和自然数(正整数)的幂，在最后一步中，我们收集了与 n^3 成比例的所有项，这是主导力量。因此，我们可以安全地得出结论: T(n) = O(S(n)) = O(n^3) .

---

幼稚的方法可能在哪里失败？考虑以下示例:

在哪里N是等于 n 的初始值的参数，即:

现在，如果采用天真的方法，我们可以做出哪些假设？

1. 自 n = N最初，假设复杂度的下限 简单地通过假设 n = N 给出。对于 log 的所有条款。但这给出了 0!
2. 假设停止条件是n = 1 , 最大项也是最后一项 - log N .显然有N项在整个总和中，所以最终的复杂度是O(N log N) = O(n log n) .

(2) 看似合理，但是否正确？

让我们使用上面的过程:

我们在 (1) (2) 和 Stirling's approximation 中使用了一些对数规则在(3)中。因此最终复杂度T(n)是:

如您所见，朴素的乘法方法给了我们错误的结果 O(n log n)而不是 O(n) .

为什么我选择这个相当深奥的反例让您感到厌烦(抱歉!)？ Because I have seen this mistake made before .