数据结构与算法 / 系统课时
大 Omega 与大 Theta
大 Omega 与大 Theta
只会写大 O 容易把“最多增长多快”误当成完整复杂度结论。本课用渐进下界与紧确界补全分析框架,并通过一个可运行示例观察函数比值如何稳定到常数范围。
学习目标
- 理解大 Omega 表示渐进下界,大 Theta 表示渐进紧确界。
- 能用常数、阈值和不等式证明函数之间的渐进关系。
- 能区分大 O、大 Omega 与大 Theta,避免把它们当作运行场景标签。
两种记号解决什么问题
大 O 只给出上界。例如,写成“某算法是 ”只说明增长速度最终不会超过某个常数倍的 ,并不自动说明它确实以二次速度增长。
大 Omega 给出下界,用来说明函数至少增长得多快。若存在常数 和 ,使所有 都满足:
则记为 。
大 Theta 同时给出上界和下界。若存在常数 、 和 ,使所有 都满足:
则记为 。它表达的是:忽略常数因子和低阶项后,两个函数具有相同的增长级别。

从定义判断一个函数
考虑:
当 时, 且 ,因此:
取 、、,即可得到 。由于紧确界同时包含下界和上界,所以也能推出 与 。
只知道 和 时, 或 都符合。还可令 在偶数规模取 n,在奇数规模取 n²。它符合这两条界,但对 n 或 n² 都没有紧确界。
可运行示例:观察比值趋于常数
将下面的代码保存为 omega_theta_demo.py。程序计算 。比值逐渐接近常数 3,可以帮助建立直觉,但有限次采样不能替代严格证明。
def f(n: int) -> int:
return 3 * n * n + 5 * n + 7
def main() -> None:
# 比较不同输入规模下 f(n) 与 n^2 的倍数关系
for n in (10, 100, 1000):
ratio = f(n) / (n * n)
print(f"n={n}, f(n)/n^2={ratio:.4f}")
if __name__ == "__main__":
main()运行命令:
python omega_theta_demo.py预期输出
n=10, f(n)/n^2=3.5700
n=100, f(n)/n^2=3.0507
n=1000, f(n)/n^2=3.0050输出显示低阶项的影响随 增大而减弱,主导项 决定了最终增长级别。
用奇偶子序列检验边界
下面输出 mixed 相对 n 和 n² 的比值,以及 oscillating 相对 n 的比值。对 mixed,奇数规模的 取 n,故无法给出 。偶数规模的 取 ,故无法给出 。
from fractions import Fraction
def mixed(n):
return n if n % 2 == 0 else n * n
def oscillating(n):
return (2 if n % 2 == 0 else 3) * n
for n in (10, 11, 100, 101):
print(n, Fraction(mixed(n), n), Fraction(mixed(n), n*n),
Fraction(oscillating(n), n))oscillating 的比值在 2 和 3 之间交替,无极限,仍有 ,所以是 。定义要求统一的上下界常数,允许比值在常数范围内变化。
易混淆点
| 记号 | 表达含义 | 是否一定紧确 |
|---|---|---|
| 渐进上界,最终不超过常数倍 | 否 | |
| 渐进下界,最终不少于常数倍 | 否 | |
| 上界与下界同阶 | 是 |
大 O、大 Omega 和大 Theta 描述的是函数之间的渐进关系,不等同于“最坏情况、最好情况、平均情况”。先明确是在约束某个实现的最好、平均或最坏代价函数,还是论证整个问题在给定模型中的下界。某个实现的下界不能直接推广到所有算法。
本课练习
- 证明 。给出可行的 、 和 ,并写出完整不等式链。
- 判断“”是否成立。说明从哪个输入阈值开始成立,并解释为什么不能据此直接写成 。
本课总结
- 大 Omega 描述渐进下界,大 Theta 描述上下界一致的紧确增长级别。
- 证明渐进关系的关键是找到正的常数因子与统一阈值,而不是只观察若干样本。
- 大 Theta 能同时推出对应的大 O 与大 Omega,但松散的上下界不一定能合成为紧确界。
下一课预告
下一课将学习“常见增长函数比较”,把常数、对数、线性、多项式和指数函数放在同一尺度下,建立判断算法可扩展性的直觉。