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

Question

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

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

Answer 1

你可以把big-O当作任何函数，然后尝试解决递归问题。在这种情况下，你可以做

T(n)   = T(n-4)  + O(n²)
T(n-4) = T(n-8)  + O(n²)
T(n-8) = T(n-12) + O(n²)
.
.
.
T(0) = 0

请注意 O(n²) 与 O((n - 4)²) 基本相同。

所以通过替换你达到

T(n) = O(n²) + O(n²) + O(n²) + ... + 0

您可以轻松证明此求和有 n/4 项。所以这是

T(n) = ¼n * O(n²) = O(n³)

或者，请记住任何形式的 f(n) = c*n² 函数是 O(n²)。因此，您还可以将 O(n²) 替换为此类函数之一，并使用以下不等式渐近地工作：

T(n) ≤ T(n-4) + c*n²

其余的基本相同。

Answer 2

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

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

安全的做法是 精确地 评估复发 - 即没有 O-notation，"re-apply" O-notation最后只取前导项。

我们来看例子。定义一个函数 S(n) 计算 precise 系列值：

假设递归在n <= 0时停止，则展开级数有floor(n / 4)项：

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

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

其中 N 是等于 n 的初始值的参数，即：

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

由于 n = N 最初，假设复杂度的下限简单地通过假设 n = N for all[= log 项中的 87=] 个。但这给出了 0!

假设停止条件是n = 1时，最大项也是最后- log N。显然整个求和有N项，所以最终的复杂度是O(N log N) = O(n log n).

(2) 看似有理，但是正确吗？

让我们使用上面的程序：

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

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

为什么我选择这个相当深奥的 counter-example 让您感到厌烦（抱歉！）？ Because I have seen this mistake made before.

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

Computing Tightest Big-Oh Bounds on Recurrence

algorithm

recursion

big-o

recurrence