数据结构与算法 / 系统课时
大 O 记号
大 O 记号
复杂度分析最终需要一种不依赖机器速度和常数系数的表达方式。大 O 记号通过给函数设置一个最终成立的上界,描述算法成本不会比某个增长级别更快,本课将从形式化定义、证明方法和常见误区三个层面掌握它。
学习目标
- 解释大 O 记号中的常数 、阈值 和“最终成立”。
- 为常见函数构造渐进上界证明。
- 区分合法但宽松的上界与更有信息量的紧确增长级别。
核心原理
设 表示算法成本, 表示候选上界。这里以非负成本函数为例,规模 n 取整数。当存在正常数 和阈值 ,使得所有 都满足下面的不等式时,记作 :
定义中的重点不是“小于”本身,而是可以忽略有限个较小输入,并允许用常数倍放大 。因此, 与 的常数系数和低阶项不同,但它们具有相同的二次增长级别。
对所有 ,有 且 ,所以:
选择 、 即可证明 。证明不要求找到最小的 或最小的 ,只要存在一组合法常数即可。
| 函数 | 一个合法上界 | 说明 |
|---|---|---|
| 常数项最终被线性项主导 | ||
| 增长更快 | ||
| 最高次项决定多项式阶数 | ||
| 结论正确但过于宽松 |
大 O 只表示上界,不自动表示最坏情况。最好、平均和最坏情况是对输入集合的分类;大 O、 和 是对函数增长关系的描述,两组概念不能混为一谈。
判断与证明步骤
- 明确 和候选 ,并确认它们在足够大的 上非负。
- 删除不会改变最高增长级别的常数因子和低阶项,但在正式证明中要用不等式说明。
- 构造一组 与 ,使 对所有 成立。
- 若 在尾部始终大于 0,就可看比值 。如果任意阈值之后的比值都无上界,便不存在所需常数。只要某个无限子序列上比值无界就足够。若 在任意大的规模还可能取 0,则直接用定义的不等式。
例如, 不是 ,因为 会无限增长,任何固定常数 最终都会被超过。相反, 是 ,因为当 时有 。
完整可运行示例
下面的 Python 3 程序使用已证明的 和 检查若干输入,并打印 。有限范围测试不能代替数学证明,但可以帮助验证推导与代码是否一致。
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()运行命令:
python3 big_o_demo.py预期输出
选择 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,真正保证所有 的依据仍然是前面的代数不等式。
为指定常数找反例
若有人声称 从某个阈值起成立,只需选 且 ,即可得到 。下面仅演示整数常数。对正实数 c 可用 floor(c)+1 构造同样的 n;任意实数阈值可先向上取整。
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 当成精确等式
写出 只说明 是一个渐进上界,并不表示 与 完全相等。严格集合记号也可写成 ,但算法教材常沿用等号形式。
2. 只用几个样本点下结论
有限测试无法证明不等式对所有足够大的 都成立。正确做法是构造统一的常数 和阈值 ,再完成代数证明。
3. 误把大 O 等同于最坏情况
一个算法的最好情况、平均情况和最坏情况都可以分别使用大 O 描述。分析时应先说明正在讨论哪一种输入情况,再给出相应的渐进上界。
本课练习
- 为 构造一组 和 ,证明它属于 ,并写出完整不等式链。
- 判断 是否属于 ,说明需要从多大的 开始处理 的下界。
- 证明 不属于 。要求使用反证法或比值无界的方法,而不是只列举有限个数值。
本课总结
- 大 O 通过常数 和阈值 描述最终成立的渐进上界。
- 常数因子和低阶项可以忽略,但正式证明必须给出对所有足够大输入成立的不等式。
- 合法上界可能很宽松;要表达精确增长级别,还需要结合渐进下界与紧确界。
下一课预告
下一阶段将继续学习渐进下界与紧确界,理解如何用不同记号同时描述算法增长的上限、下限和精确阶。