如何使用 Big-O 的正式定义证明 y = n^2 不属于 O(1)？
How do I prove that y = n^2 does not belong to O(1) using formal definition of Big-O?
我知道在 Big-O 中分类本质上是有一个排序的“上限”，所以我从图形上理解它，我不明白如何使用 Big-O 形式定义来解决这种类型的问题问题。感谢您的帮助。
虽然有比 SO 更适合解决这个问题的平台，但由于这纯粹是数学问题，理解这一点对于在计算机科学环境中使用 big-O 也是至关重要的，所以我喜欢这个问题。理解您的特定示例可能会阐明什么是大 O，并提供一些实用的直觉。所以我会尝试解释：
我们有一个函数 f(n) = n2。为了证明它不在 O(1) 中，我们必须证明它比函数 g(n) = c 增长得更快，其中c 是一些常量。换句话说，f(n) > g(n) 足够大 n.
足够大是什么意思？这意味着对于任何常数 c，我们可以找到一个 N 使得 f(n) > g(n) 所有 n > N.
这就是我们定义渐近行为的方式。您的常量函数可能大于 f(n)，但随着 n 足够大，您最终会达到 f(n) 永远保持更大。如何证明？
无论您选择什么常数 c - 无论大小 - 我们都可以构造我们的 N。让我们说 N = √c。因为c是常数，所以√c.
也是
现在，我们有 f(n) = n2 > c = g(n) 每当 n > √c.
因此，f(n)不在O(1)中。 □
这里关键是我们找到了一个常数N（也就是取决于我们的常数c 但不在我们的变量 n) 上，因此这种不等式成立。它可能需要花一些时间来思考，但是做一些其他简单的例子可以帮助获得直觉。
我知道在 Big-O 中分类本质上是有一个排序的“上限”，所以我从图形上理解它，我不明白如何使用 Big-O 形式定义来解决这种类型的问题问题。感谢您的帮助。
虽然有比 SO 更适合解决这个问题的平台，但由于这纯粹是数学问题，理解这一点对于在计算机科学环境中使用 big-O 也是至关重要的，所以我喜欢这个问题。理解您的特定示例可能会阐明什么是大 O，并提供一些实用的直觉。所以我会尝试解释：
我们有一个函数 f(n) = n2。为了证明它不在 O(1) 中，我们必须证明它比函数 g(n) = c 增长得更快，其中c 是一些常量。换句话说，f(n) > g(n) 足够大 n.
足够大是什么意思？这意味着对于任何常数 c，我们可以找到一个 N 使得 f(n) > g(n) 所有 n > N.
这就是我们定义渐近行为的方式。您的常量函数可能大于 f(n)，但随着 n 足够大，您最终会达到 f(n) 永远保持更大。如何证明？
无论您选择什么常数 c - 无论大小 - 我们都可以构造我们的 N。让我们说 N = √c。因为c是常数，所以√c.
也是现在，我们有 f(n) = n2 > c = g(n) 每当 n > √c.
因此，f(n)不在O(1)中。 □
这里关键是我们找到了一个常数N（也就是取决于我们的常数c 但不在我们的变量 n) 上，因此这种不等式成立。它可能需要花一些时间来思考，但是做一些其他简单的例子可以帮助获得直觉。