无法透彻理解Big O的形式化定义，如何确定常数c、见证n及相关边界？

形式化定义 #

首先给出标准大O形式化定义：
对于两个定义在正整数集上的非负函数f(n)和g(n)，若存在正的常数c和正整数n₀，使得所有满足n ≥ n₀的n，都有

0 ≤ f(n) ≤ c·g(n)

则称f(n)属于复杂度类O(g(n))。其中n₀就是你提到的「见证」，也叫边界。

核心逻辑说明 #

大O记号本质是描述函数在输入规模n趋近于无穷时的渐进上界，只关心大规模输入下的增长速度，完全忽略小输入规模的特殊情况，所以不需要满足所有n都符合不等式，只要过了n₀这个边界之后永远成立即可。

c和边界n₀的构造方法 #

你不需要找到最小的c和n₀，只要能找到任意一组符合要求的正c和n₀即可，通用构造思路如下：

• 先确定g(n)，通常我们取f(n)的最高次项且去掉系数的形式，以得到最紧的上界
• 将f(n)的所有低次项，通过限定n ≥ 某个值的方式，放缩为不超过某个常数 * g(n)的形式
• 把所有项的系数相加，得到最终的c，刚才限定的n的阈值就是边界n₀

示例演示 #

以常见的f(n) = 2n² + 3n + 5，要证明f(n) ∈ O(n²)为例：

• 第一步取g(n) = n²
• 第二步放缩低次项：
  • 当n ≥ 1时，3n ≤ 3n²
  • 当n ≥ 1时，5 ≤ 5n²
• 第三步合并放缩结果：2n² + 3n +5 ≤ 2n² +3n² +5n² = 10n²

即可得到一组可行解：c=10，n₀=1。你也可以通过提高边界值得到更小的c，比如当n ≥ 3时，3n ≤ n²，5 ≤ n²，此时f(n) ≤ 2n² +n² +n² =4n²，对应c=4，n₀=3，两组解都是有效的。

常见误区澄清 #

• 大O给出的是上界，不是唯一上界：比如3n+1 ∈ O(n)是最紧上界，但你说3n+1 ∈ O(n²)也是符合定义的，只是工程上我们只会用最紧的上界描述算法复杂度
• c不需要是整数，只要是正实数即可，不需要找最小的c，只要存在就满足定义要求

内容的提问来源于stack exchange，提问作者CaliCrunch