数据结构与算法 / 系统课时

大 O 记号

大 O 记号

复杂度分析最终需要一种不依赖机器速度和常数系数的表达方式。大 O 记号通过给函数设置一个最终成立的上界,描述算法成本不会比某个增长级别更快,本课将从形式化定义、证明方法和常见误区三个层面掌握它。

学习目标

  • 解释大 O 记号中的常数 cc、阈值 n0n_0 和“最终成立”。
  • 为常见函数构造渐进上界证明。
  • 区分合法但宽松的上界与更有信息量的紧确增长级别。

核心原理

设 f(n)f(n) 表示算法成本,g(n)g(n) 表示候选上界。这里以非负成本函数为例,规模 n 取整数。当存在正常数 cc 和阈值 n0n_0,使得所有 n≥n0n\ge n_0 都满足下面的不等式时,记作 f(n)=O(g(n))f(n)=O(g(n)):

f(n)=O(g(n))  ⟺  ∃c>0,∃n0>0,∀n≥n0:0≤f(n)≤c g(n)f(n)=O(g(n)) \iff \exists c>0,\exists n_0>0,\forall n\ge n_0:0\le f(n)\le c\,g(n)

定义中的重点不是“小于”本身,而是可以忽略有限个较小输入,并允许用常数倍放大 g(n)g(n)。因此,3n2+5n+23n^2+5n+2 与 n2n^2 的常数系数和低阶项不同,但它们具有相同的二次增长级别。

对所有 n≥1n\ge1,有 5n≤5n25n\le5n^2 且 2≤2n22\le2n^2,所以:

3n2+5n+2≤3n2+5n2+2n2=10n23n^2+5n+2\le3n^2+5n^2+2n^2=10n^2

选择 c=10c=10、n0=1n_0=1 即可证明 3n2+5n+2=O(n2)3n^2+5n+2=O(n^2)。证明不要求找到最小的 cc 或最小的 n0n_0,只要存在一组合法常数即可。

函数 f(n)f(n) 一个合法上界 说明
7n+207n+20 O(n)O(n) 常数项最终被线性项主导
nlog⁡n+3nn\log n+3n O(nlog⁡n)O(n\log n) nlog⁡nn\log n 增长更快
4n2+n+14n^2+n+1 O(n2)O(n^2) 最高次项决定多项式阶数
n2n^2 O(n3)O(n^3) 结论正确但过于宽松

大 O 只表示上界,不自动表示最坏情况。最好、平均和最坏情况是对输入集合的分类;大 O、Ω\Omega 和 Θ\Theta 是对函数增长关系的描述,两组概念不能混为一谈。

判断与证明步骤

  1. 明确 f(n)f(n) 和候选 g(n)g(n),并确认它们在足够大的 nn 上非负。
  2. 删除不会改变最高增长级别的常数因子和低阶项,但在正式证明中要用不等式说明。
  3. 构造一组 c>0c>0 与 n0>0n_0>0,使 f(n)≤cg(n)f(n)\le c g(n) 对所有 n≥n0n\ge n_0 成立。
  4. 若 g(n)g(n) 在尾部始终大于 0,就可看比值 f(n)/g(n)f(n)/g(n)。如果任意阈值之后的比值都无上界,便不存在所需常数。只要某个无限子序列上比值无界就足够。若 gg 在任意大的规模还可能取 0,则直接用定义的不等式。

例如,n2n^2 不是 O(n)O(n),因为 n2/n=nn^2/n=n 会无限增长,任何固定常数 cc 最终都会被超过。相反,nn 是 O(n2)O(n^2),因为当 n≥1n\ge1 时有 n≤n2n\le n^2。

完整可运行示例

下面的 Python 3 程序使用已证明的 c=10c=10 和 n0=1n_0=1 检查若干输入,并打印 f(n)/n2f(n)/n^2。有限范围测试不能代替数学证明,但可以帮助验证推导与代码是否一致。

python
def f(n: int) -> int:
    return 3 * n * n + 5 * n + 2

def main() -> None:
    c = 10
    n0 = 1
    print(f"选择 c={c}, n0={n0}")

    for n in [1, 2, 10, 100]:
        ratio = f(n) / (n * n)
        holds = f(n) <= c * n * n
        print(
            f"n={n:>3}, f(n)/n^2={ratio:.4f}, "
            f"不等式={holds}"
        )

    checked = all(f(n) <= c * n * n for n in range(n0, 101))
    print("有限范围验证:", checked)

if __name__ == "__main__":
    main()

运行命令:

bash
python3 big_o_demo.py

预期输出

text
选择 c=10, n0=1
n=  1, f(n)/n^2=10.0000, 不等式=True
n=  2, f(n)/n^2=6.0000, 不等式=True
n= 10, f(n)/n^2=3.5200, 不等式=True
n=100, f(n)/n^2=3.0502, 不等式=True
有限范围验证: True

比值逐渐接近最高次项系数 3,并始终不超过 10。程序只检查到 100,真正保证所有 n≥1n\ge1 的依据仍然是前面的代数不等式。

为指定常数找反例

若有人声称 n2≤cnn^2\le cn 从某个阈值起成立,只需选 n≥n0n\ge n_0 且 n>cn>c,即可得到 n2>cnn^2>cn。下面仅演示整数常数。对正实数 c 可用 floor(c)+1 构造同样的 n;任意实数阈值可先向上取整。

python
def counterexample(c, n0):
    """c 与 n0 取正整数时,为 n² <= c*n 找一个反例。"""
    if c < 1 or n0 < 1:
        raise ValueError("c 与 n0 必须为正整数")
    n = max(n0, c + 1)
    assert n >= n0 and n * n > c * n
    return n

print(counterexample(10, 1))
print(counterexample(10, 100))

输出 11、100,第二例即使把阈值增大到 100 也能找到反例。

常见错误

1. 把大 O 当成精确等式

写出 f(n)=O(n2)f(n)=O(n^2) 只说明 n2n^2 是一个渐进上界,并不表示 f(n)f(n) 与 n2n^2 完全相等。严格集合记号也可写成 f∈O(n2)f\in O(n^2),但算法教材常沿用等号形式。

2. 只用几个样本点下结论

有限测试无法证明不等式对所有足够大的 nn 都成立。正确做法是构造统一的常数 cc 和阈值 n0n_0,再完成代数证明。

3. 误把大 O 等同于最坏情况

一个算法的最好情况、平均情况和最坏情况都可以分别使用大 O 描述。分析时应先说明正在讨论哪一种输入情况,再给出相应的渐进上界。

本课练习

  1. 为 6n+126n+12 构造一组 cc 和 n0n_0,证明它属于 O(n)O(n),并写出完整不等式链。
  2. 判断 nlog⁡n+100nn\log n+100n 是否属于 O(nlog⁡n)O(n\log n),说明需要从多大的 n0n_0 开始处理 log⁡n\log n 的下界。
  3. 证明 n2n^2 不属于 O(n)O(n)。要求使用反证法或比值无界的方法,而不是只列举有限个数值。

本课总结

  • 大 O 通过常数 cc 和阈值 n0n_0 描述最终成立的渐进上界。
  • 常数因子和低阶项可以忽略,但正式证明必须给出对所有足够大输入成立的不等式。
  • 合法上界可能很宽松;要表达精确增长级别,还需要结合渐进下界与紧确界。

下一课预告

下一阶段将继续学习渐进下界与紧确界,理解如何用不同记号同时描述算法增长的上限、下限和精确阶。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

大 O 记号

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通