algorithm - 在算法分析过程中寻找上限有什么不同的行为？

Question

我正在学习算法分析和大 O 表示法。有以下练习示例供引用:

示例 1:找到 f(n) = 3n + 8 的上限

解: 3n + 8 ≤ 4n，对于所有 n ≥ 8

       ∴ 3n + 8 = O(n) with c = 4 and n0 = 8

另一个，

示例 2: 找到 f(n) = n^2 + 1 的上限

解: n^2 + 1 ≤ 2(n^2)，对于所有 n ≥ 1

       ∴ n^2 + 1 = O(n^2) with c = 2 and n0 = 1

现在是下一个例子，也是困扰我的例子，

示例 3: 找到 f(n) = 2n^3 – 2n^2 的上限

解: 2n^3 – 2n^2 ≤ 2n^3，对于所有 n ≥ 1

       ∴ 2n^3 – 2n^2 = O(n^3 ) with c = 2 and n0 = 1

为什么我们在上一个例子中使用 2n^3 进行比较？

表示在每个示例中我们都使用了更大的值，即在第一个示例中我们使用了 4n，因为方程式的最大值为 3n，

在第二个示例中，我们使用了 2(n^2)，因为 n^2 是该等式中的最大值。

这意味着在第三个等式中我们应该使用 3(n^3) 而不是 2(n^2)。

也许我在这里没有得到什么，你能详细说明缺失的部分吗？

这里c和n0的需求是什么。 n0 是我们考虑给定算法的增长率的起点，但为什么是 c？我是算法分析的新手。

Answer 1

替换项以便所有指数都相同。对于上限，您希望用更大的值替换它们。增加指数将为正项产生更大的值，但对于负项，您可以将它们替换为 0，从而删除项。

对于 3n + 8 , 3n + n是一个上限，因为 8 <= n对于 n > n0 .

对于 n^2 + 1 , n^2 + n^2是一个上限，因为 1 <= n^2对于 n > n0 .

对于 3n^3 - 2n^2 , 3n^3 + 0是一个上限，因为 -2n^2 <= 0对于 n > n0 .

---

c和 n0是必需的，因为它们是 Big-O 定义的一部分:

`f(n) = O(g(n))` means that `f(n) <= c.g(n)` for some c and large enough n

通过查找 c 的值和 n0 ，您可以证明某些函数符合此定义，其中 c是你需要相乘的 g通过使其大于f .