推理 Big O 的正式定义时遇到一些困难

Question

我的教授最近回顾了 Big O 的正式定义：

老实说，即使他向几个不同的学生解释了它，我们似乎仍然没有理解它的核心。理解上的问题主要出现在我们经历的以下例子中：

到目前为止，我的推理如下：

当您将函数的最高项乘以常数时，您会得到一个新函数，该新函数最终在给定的n处超过初始函数。他称此n为函数O(g(n))的“见证人”

这个c术语是如何创建/找到的？他多次提到边界，但没有真正说明边界的含义或如何找到/使用它们。

我认为我只需要正式定义以及这些示例如何支持定义的更坚实的基础。

Answer 1

我认为这个定义通常以 c 值和 n0 的形式表示的方式是不必要的混乱。f(n) 为 O(g(n)) 的真正含义是，当您忽略常数和低阶项时，g(n) 是 f(n) 的渐近上限（对于 g 的函数到渐近上限f 只是意味着经过某个点 g 始终大于或等于 f)。换句话说，当 n 趋向无穷大时，f(n) 的增长速度并不比 g(n) 快。

大 O 本身有点令人困惑，因为 f(n) = O(g(n)) 并不意味着 g(n) 的增长速度严格快于 f(n)。这意味着当您忽略常数和低阶项时，g(n) 的增长速度比 f(n) 快，或者以相同的速度增长（严格来说更快的是“小 o”）。表达这个概念的一个简单、正式的方式是：

也就是说，为了使该限制成立，f(n)的最高阶项至多可以是g(n)的最高阶项的常数倍。f(n) 的复杂度是 O(g(n))，当且仅当它的增长速度不快于 g(n)。

例如，f(n) = n 的复杂度为 O(g(n) = n^2)，因为经过某个点 n^2 总是大于 n。n^2 对 n 的限制是正数，因此 n 的复杂度为 O(n^2)

再举个例子，f(n) = 5n^2 + 2n 的时间复杂度为 O(g(n) = n^2)，因为在极限情况下，f(n) 只能比 g(n) 大 5 倍左右。它并不是无限大：它们以相同的速度增长。准确地说，n^2 对 (5n^2 + 3n) 的限制是 1/5，大于零，因此 5n^2 + 3n 的复杂度为 O(n^2)。希望这个基于极限的定义能够提供一些直觉，因为它在数学上与所提供的定义完全等效。

找到一个特定的常数值 c 和 x 值 n0 使得所提供的不等式成立，这只是一种特殊的方式，表明在 n 趋向无穷大的极限中，g(n) 的增长速度至少与 f(n) 一样快： f(n) 的复杂度为 O(g(n))。也就是说，如果您发现超过 c*g(n) 始终大于 f(n) 的值，则表明 f(n) 的增长速度不超过 g 的常数倍（c 倍） (n)（如果 f 的增长速度比 g 快超过一个常数倍，则不可能找到这样的 ac 和 n0）。

找到特定的 c 和 n0 值来证明 f(n) = O(g(n)) 并不存在真正的艺术。它们实际上可以是您需要它们使不平等成立的任何积极价值观。事实上，如果 f(n) = O(g(n)) 成立，那么您可以为 c 选择任何您想要的值，并且将有一些足够大的 n0 值使不等式成立，或者类似地，您可以选择您想要的任何 n0 值，如果您使 c 足够大，则不等式将成立（遵守 c 和 n0 均为正数的限制）。这就是为什么我不太喜欢大 O 的这种形式化：它不必要地特殊，并且涉及它的证明有些武断，分散了人们对主要概念的注意力，即当 n 趋于无穷大时 f 和 g 的行为。

因此，至于在实践中如何处理这个问题，请使用示例问题之一：为什么 n^2 + 3n 在 O(n^2) 中？

答案：因为 n 趋向无穷大时 n^2 / (n^2 + 3n) 的极限是 1，大于 0。

或者，如果您想要/需要以其他方式执行此操作，请为 n0 选择任何您想要的正值，并以该值计算 f 。f(1) 总是足够简单：

f(1) = 1^2 + 3*1 = 4

然后找到可以将 g(1) 乘以得到与 f(1) 相同的值的常数（或者，如果不使用 n0 = 1，则使用用于 f 的 g 的任何 n0）。

c*g(1) = 4
c*1^2  = 4
c = 4

然后，您只需将这些语句组合成一个断言，以表明存在一个正 n0 和一个常数 c，使得对于所有 n >= n0，cg(n) >= f(n)。

n^2 + 3n <= (4)n^2 for all n >= 1, implying n^2 + 3n is in O(n^2)

如果您使用这种证明方法，那么理想情况下，用于证明不等式的上述陈述应该立即显而易见。如果不是，也许您想更改 n0 以便最终的陈述更清楚地正确。我认为，如果您可以使用该路线，那么显示 g(n)/f(n) 比率的极限为正会更清晰、更直接，但这取决于您。

转向反例，使用 limit 方法很容易证明 f(n) 不在 O(g(n)) 中。为此，您只需证明 g(n) / f(n) = 0 的极限。使用第三个示例问题：nlog(n) + 2n 是 O(n) 吗？

为了以另一种方式证明它，您实际上必须证明不存在正数对 n0, c 使得对于所有 n >= n0 f(n) <= cg(n)。

不幸的是，通过使用 c=2, n0=8 表明 f(n) = nlogn + 2n 在 O(nlogn) 中，但无法证明 f(n) 是否在 O(n) 中（表明函数属于更高复杂度的类）并不意味着它不是一个较低复杂度的类）。

要了解为什么会出现这种情况，我们还可以使用相同的 c 和 n0 值来显示 a(n) = n 在 g(n) = nlogn 中（对于所有 n >= 8，n <= 2(nlog(n)，暗示 n 在 O(nlogn))`) 中，但 a(n)=n 显然在O(n) 中。也就是说，用这种方法要证明 f(n)=nlogn + 2n不在O(n) 范围内，不能仅仅证明它在 O(nlogn) 范围内。你必须证明，无论你选择什么 n0，你永远找不到足够大的 ac 值，使得 f(n) >= c(n) 对于所有 n >= n0 。证明这样一对数字不存在并非不可能，但相对而言，这是一件棘手的事情（并且本身可能涉及极限方程，或矛盾证明）。

总而言之，如果 g(n) 对 f(n) 的限制为正，则 f(n) 的复杂度为 O(g(n))，这意味着 f(n) 的增长速度不会比 g(n) 快）。类似地，找到一个常数 c 和 x 值 n0，超过该值 cg(n) >= f(n) 表明 f(n) 不能比 g(n) 渐近增长得更快，这意味着当丢弃常数和低阶项时，g( n) 是 f(n) 的有效上限。