大Ω记号写作 Ω,用于描述函数增长的渐近下界。按照计算机科学中的标准含义,f(n)=Ω(g(n)) 表示当 n 超过某个阈值后,f(n) 至少为 g(n) 的某个正常数倍。它广泛用于计算复杂性中,表示运行时间、内存消耗及其他资源需求的下界。这个记号描述的是函数之间的关系;它本身并不说明分析针对的是最好情况、平均情况还是最坏情况。
形式定义
设 f 和 g 是定义在正整数上的实值函数,且当输入充分大时,两个函数均非负。如果存在常数 c>0 和 n0,使得
0≤cg(n)≤f(n)for every n≥n0.
则称
f(n)=Ω(g(n))
这些常数必须与 n 无关。重要的是它们是否存在,其具体取值通常并不重要。
例如,设
f(n)=3n2−5n+2.
对于每个整数 n≥2,都有
f(n)−n2=2n2−5n+2=(2n−1)(n−2)≥0.
因此,取 c=1、n0=2,可得 f(n)=Ω(n2)。这个函数也属于 Ω(n) 和 Ω(1):一个下界不一定是所能给出的最强下界。
严格来说,Ω(g) 表示一个函数集合。因此,这一命题的集合论写法是
f∈Ω(g)
惯用表达式 f=Ω(g) 虽然广泛使用,但其中的等号不应视为具有通常对称性的等号。
同一定义也适用于实变量趋于无穷时的函数,此时要求不等式对每个充分大的实数自变量都成立。
与其他渐近记号的关系
大Ω记号属于渐近记号这一类记号,它们在比较增长速度时,忽略常数因子以及定义域有界部分上的行为。
| 记号 |
对于充分大时非负的函数,其含义为 |
| f(n)=O(g(n)) |
当自变量充分大时,f 不超过 g 的某个正常数倍。 |
| f(n)=Ω(g(n)) |
当自变量充分大时,f 不小于 g 的某个正常数倍。 |
| f(n)=Θ(g(n)) |
上述两种界均成立,所用的常数可以不同。 |
| f(n)=ω(g(n)) |
对于每个正常数 c,当自变量充分大时,均有 f(n)≥cg(n)。 |
特别地,大O记号与大Ω记号互为对偶:
f(n)=Ω(g(n))⟺g(n)=O(f(n)).
用大Θ记号表示的渐近紧界满足
f(n)=Θ(g(n))⟺f(n)=O(g(n)) and f(n)=Ω(g(n)).
小ω记号比大Ω记号更强。对于充分大时为正的 g,有
f(n)=ω(g(n))⟺g(n)f(n)⟶+∞.
因此,n2=Ω(n2),但 n2=ω(n2)。相比之下,n2=ω(n)。
在算法分析中的含义
分析算法时,大Ω记号可以描述任何明确定义的资源函数的下界,常见例子包括时间复杂度和空间复杂度。
设 tA(x) 为算法 A 在输入 x 上的运行时间。假定最大值和最小值均存在,定义
Tworst(n)=∣x∣=nmaxtA(x),Tbest(n)=∣x∣=nmintA(x).
这些函数可以用来表述不同的结论:
- Tworst(n)=Ω(g(n)) 表示,对于每个充分大的输入规模,都存在某个输入,至少需要 cg(n) 的时间。
- Tbest(n)=Ω(g(n)) 表示,对于每个充分大的输入规模,该规模下的每个输入都至少需要 cg(n) 的时间。
- 平均情况下界涉及指定输入分布下的期望值。
对于随机化算法,也可以针对算法内部的随机性取期望。期望时间的下界并不自动意味着每次执行都满足同样的下界。
下界并不意味着最好情况复杂度
有时,人们会非正式地将大Ω记号称为“最好情况记号”。这种说法是错误的。最好情况分析和最坏情况分析决定研究的是哪个资源函数;大Ω记号则规定该函数的界的方向。
例如,在未排序的数组(数据结构)中进行顺序查找,可能在第一次比较后就结束。因此,其最好情况运行时间为 Θ(1)。它的最坏情况运行时间为 Θ(n),因而也是 Ω(n)。后一个结论并不意味着每次查找都需要线性时间。
算法下界与问题下界
某个算法的下界不同于整个计算问题的下界。
证明某个特定的排序算法需要 Ω(nlogn) 的时间,并不能证明所有排序算法都需要这么多时间。问题层面的下界必须涵盖指定计算模型所允许的所有算法。
对 n 个互不相同的元素进行基于比较的排序时,确定性算法必须区分 n! 种可能的输入排列。因此,二叉比较树在最坏情况下的高度至少为
⌈log2(n!)⌉=Ω(nlogn).
这个下界适用于比较模型。它并不排除在不同假设下采用更快的排序方法,例如利用整数键值范围有界这一特点的方法。归并排序的最坏情况上界为 O(nlogn),在渐近阶上与比较模型的下界一致。
如何证明大Ω下界
直接利用不等式
最直接的证明方法是给出合适的常数 c 和 n0。
对于首项系数为正的多项式
p(n)=aknk+ak−1nk−1+⋯+a0,ak>0,
当 n 充分大时,所有低次项之和的绝对值至多为 2aknk。因此,对于充分大的 n,有
p(n)≥2aknk
由此证明 p(n)=Ω(nk)。
比值判别法
如果 g(n)>0 在 n 充分大时成立,则
f(n)=Ω(g(n))⟺n→∞liminfg(n)f(n)>0,
其中,下极限可以为 +∞。
特别地,如果比值的通常极限存在且为正,无论是有限正值还是正无穷,都能据此确立大Ω下界。如果极限为零,则该下界不成立。
通常意义下的极限并非必需。例如,
f(n)=n(2+(−1)n)
的比值 f(n)/n 在 1 和 3 之间交替变化。这个比值不收敛,但仍有 f(n)=Ω(n)。
计数与不可避免的工作量
算法下界往往来自所选模型下无法避免的工作,例如读取必需的输入项、显式写出输出,或区分足够多种可能的答案。
这类论证需要精确的假设。在每次操作只能写出常数个输出项的模型中,显式生成 m 个输出项需要 Ω(m) 次输出操作。返回压缩表示或指向已有数据的引用属于不同的任务,不一定满足同样的下界。
性质与局限
对于充分大时非负的函数,大Ω关系具有传递性:
f=Ω(g),g=Ω(h)⟹f=Ω(h).
将其中任意一个函数乘以固定的正常数,不会改变这一关系。修改有限多个函数值也不会产生影响。
其渐近性质带来以下局限:
- 它不给出精确的开销。 诸如 T(n)=Ω(n) 这样的陈述,既不指定具体运行时间,也不指定不等式开始成立的阈值。
- 它不一定是紧界。 n 和 n3 都属于 Ω(n)。
- 它要求在自变量充分大时有统一的下界。 仅在某个无穷子序列上取大值并不足够。一个在偶数输入上等于 n2、在奇数输入上等于 1 的函数,不属于 Ω(n)。
- 它依赖于计算模型。 将任意精度算术运算视为一次操作,与逐一统计比特操作,可能得出不同的界。
- 它要求明确趋于极限的方式。 当输入有多个参数时,诸如 T(n,m)=Ω(nm) 这样的断言,必须说明涵盖哪些参数取值,以及所用常数是否对这些取值统一适用。
历史上的约定
符号 Ω 在渐近分析中并非始终具有统一的含义。在解析数论的部分领域所采用的哈代–李特尔伍德约定中,f=Ω(g) 大致表示相对于 g,f 在渐近意义下并非可忽略,而不是断言在自变量充分大时存在一个正的下界。
对于正值函数 g,这一约定通常表述为
x→∞limsupg(x)f(x)>0.
它允许比值仅沿某个子序列保持显著大小,并不要求计算机科学中的不等式对每个充分大的自变量都成立。当自变量充分大时要求下界成立的约定由高德纳倡导,如今已成为算法分析中的标准。因此,在不同数学领域之间切换时,必须核实所采用的定义,而不能仅凭符号推断其含义。