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

大 Omega 与大 Theta

大 Omega 与大 Theta

只会写大 O 容易把“最多增长多快”误当成完整复杂度结论。本课用渐进下界与紧确界补全分析框架,并通过一个可运行示例观察函数比值如何稳定到常数范围。

学习目标

  • 理解大 Omega 表示渐进下界,大 Theta 表示渐进紧确界。
  • 能用常数、阈值和不等式证明函数之间的渐进关系。
  • 能区分大 O、大 Omega 与大 Theta,避免把它们当作运行场景标签。

两种记号解决什么问题

大 O 只给出上界。例如,写成“某算法是 O(n2)O(n^2)”只说明增长速度最终不会超过某个常数倍的 n2n^2,并不自动说明它确实以二次速度增长。

大 Omega 给出下界,用来说明函数至少增长得多快。若存在常数 c>0c>0 和 n0n_0,使所有 n≥n0n\ge n_0 都满足:

0≤cg(n)≤f(n)0 \le c g(n) \le f(n)

则记为 f(n)=Ω(g(n))f(n)=\Omega(g(n))。

大 Theta 同时给出上界和下界。若存在常数 c1>0c_1>0、c2>0c_2>0 和 n0n_0,使所有 n≥n0n\ge n_0 都满足:

0≤c1g(n)≤f(n)≤c2g(n)0 \le c_1 g(n) \le f(n) \le c_2 g(n)

则记为 f(n)=Θ(g(n))f(n)=\Theta(g(n))。它表达的是:忽略常数因子和低阶项后,两个函数具有相同的增长级别。

大 Omega 与大 Theta 的边界关系

从定义判断一个函数

考虑:

f(n)=3n2+5n+7f(n)=3n^2+5n+7

当 n≥1n\ge 1 时,5n≤5n25n\le 5n^2 且 7≤7n27\le 7n^2,因此:

3n2≤f(n)≤15n23n^2 \le f(n) \le 15n^2

取 c1=3c_1=3、c2=15c_2=15、n0=1n_0=1,即可得到 f(n)=Θ(n2)f(n)=\Theta(n^2)。由于紧确界同时包含下界和上界,所以也能推出 f(n)=Ω(n2)f(n)=\Omega(n^2) 与 f(n)=O(n2)f(n)=O(n^2)。

只知道 f(n)=O(n2)f(n)=O(n^2) 和 f(n)=Ω(n)f(n)=\Omega(n) 时,f(n)=nf(n)=n 或 f(n)=n2f(n)=n^2 都符合。还可令 ff 在偶数规模取 n,在奇数规模取 n²。它符合这两条界,但对 n 或 n² 都没有紧确界。

可运行示例:观察比值趋于常数

将下面的代码保存为 omega_theta_demo.py。程序计算 f(n)/n2f(n)/n^2。比值逐渐接近常数 3,可以帮助建立直觉,但有限次采样不能替代严格证明。

python
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()

运行命令:

bash
python omega_theta_demo.py

预期输出

text
n=10, f(n)/n^2=3.5700
n=100, f(n)/n^2=3.0507
n=1000, f(n)/n^2=3.0050

输出显示低阶项的影响随 nn 增大而减弱,主导项 3n23n^2 决定了最终增长级别。

用奇偶子序列检验边界

下面输出 mixed 相对 n 和 n² 的比值,以及 oscillating 相对 n 的比值。对 mixed,奇数规模的 f(n)/nf(n)/n 取 n,故无法给出 O(n)O(n)。偶数规模的 f(n)/n2f(n)/n^2 取 1/n1/n,故无法给出 Ω(n2)\Omega(n^2)。

python
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 之间交替,无极限,仍有 2n≤f(n)≤3n2n\le f(n)\le 3n,所以是 Θ(n)\Theta(n)。定义要求统一的上下界常数,允许比值在常数范围内变化。

易混淆点

记号 表达含义 是否一定紧确
O(g(n))O(g(n)) 渐进上界,最终不超过常数倍 g(n)g(n) 否
Ω(g(n))\Omega(g(n)) 渐进下界,最终不少于常数倍 g(n)g(n) 否
Θ(g(n))\Theta(g(n)) 上界与下界同阶 是

大 O、大 Omega 和大 Theta 描述的是函数之间的渐进关系,不等同于“最坏情况、最好情况、平均情况”。先明确是在约束某个实现的最好、平均或最坏代价函数,还是论证整个问题在给定模型中的下界。某个实现的下界不能直接推广到所有算法。

本课练习

  1. 证明 7n+20=Θ(n)7n+20=\Theta(n)。给出可行的 c1c_1、c2c_2 和 n0n_0,并写出完整不等式链。
  2. 判断“nlog⁡2n=Ω(n)n\log_2 n=\Omega(n)”是否成立。说明从哪个输入阈值开始成立,并解释为什么不能据此直接写成 Θ(n)\Theta(n)。

本课总结

  • 大 Omega 描述渐进下界,大 Theta 描述上下界一致的紧确增长级别。
  • 证明渐进关系的关键是找到正的常数因子与统一阈值,而不是只观察若干样本。
  • 大 Theta 能同时推出对应的大 O 与大 Omega,但松散的上下界不一定能合成为紧确界。

下一课预告

下一课将学习“常见增长函数比较”,把常数、对数、线性、多项式和指数函数放在同一尺度下,建立判断算法可扩展性的直觉。

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

目录与阅读设置

阅读设置

17

记录一个想法

大 Omega 与大 Theta

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

登录哪都通