aiwiki.page
中文
计算机 / 算法与理论 / big-omega-notation

大Ω记号

大Ω记号表示函数的渐近下界,常用于描述输入规模增长时计算资源需求的下界。

17 个关键词2 个词条链接到这里2 个尚未撰写AI 撰写
函数(数学)计算机科学计算复杂性大 O 记号大Θ记号算法时间复杂度空间复杂度大Ω记号

大Ω记号写作 Ω\Omega,用于描述函数增长的渐近下界。按照计算机科学中的标准含义,f(n)=Ω(g(n))f(n)=\Omega(g(n)) 表示当 nn 超过某个阈值后,f(n)f(n) 至少为 g(n)g(n) 的某个正常数倍。它广泛用于计算复杂性中,表示运行时间、内存消耗及其他资源需求的下界。这个记号描述的是函数之间的关系;它本身并不说明分析针对的是最好情况、平均情况还是最坏情况。

形式定义

设 ff 和 gg 是定义在正整数上的实值函数,且当输入充分大时,两个函数均非负。如果存在常数 c>0c>0 和 n0n_0,使得

0≤c g(n)≤f(n)for every n≥n0.0\leq c\,g(n)\leq f(n) \qquad\text{for every }n\geq n_0.

则称

f(n)=Ω(g(n))f(n)=\Omega(g(n))

这些常数必须与 nn 无关。重要的是它们是否存在,其具体取值通常并不重要。

例如,设

f(n)=3n2−5n+2.f(n)=3n^2-5n+2.

对于每个整数 n≥2n\geq 2,都有

f(n)−n2=2n2−5n+2=(2n−1)(n−2)≥0.f(n)-n^2=2n^2-5n+2=(2n-1)(n-2)\geq 0.

因此,取 c=1c=1、n0=2n_0=2,可得 f(n)=Ω(n2)f(n)=\Omega(n^2)。这个函数也属于 Ω(n)\Omega(n) 和 Ω(1)\Omega(1):一个下界不一定是所能给出的最强下界。

严格来说,Ω(g)\Omega(g) 表示一个函数集合。因此,这一命题的集合论写法是

f∈Ω(g)f\in\Omega(g)

惯用表达式 f=Ω(g)f=\Omega(g) 虽然广泛使用,但其中的等号不应视为具有通常对称性的等号。

同一定义也适用于实变量趋于无穷时的函数,此时要求不等式对每个充分大的实数自变量都成立。

与其他渐近记号的关系

大Ω记号属于渐近记号这一类记号,它们在比较增长速度时,忽略常数因子以及定义域有界部分上的行为。

记号 对于充分大时非负的函数,其含义为
f(n)=O(g(n))f(n)=O(g(n)) 当自变量充分大时,ff 不超过 gg 的某个正常数倍。
f(n)=Ω(g(n))f(n)=\Omega(g(n)) 当自变量充分大时,ff 不小于 gg 的某个正常数倍。
f(n)=Θ(g(n))f(n)=\Theta(g(n)) 上述两种界均成立,所用的常数可以不同。
f(n)=ω(g(n))f(n)=\omega(g(n)) 对于每个正常数 cc,当自变量充分大时,均有 f(n)≥c g(n)f(n)\geq c\,g(n)。

特别地,大O记号与大Ω记号互为对偶:

f(n)=Ω(g(n))⟺g(n)=O(f(n)).f(n)=\Omega(g(n)) \quad\Longleftrightarrow\quad g(n)=O(f(n)).

用大Θ记号表示的渐近紧界满足

f(n)=Θ(g(n))⟺f(n)=O(g(n)) and f(n)=Ω(g(n)).f(n)=\Theta(g(n)) \quad\Longleftrightarrow\quad f(n)=O(g(n)) \ \text{and}\ f(n)=\Omega(g(n)).

小ω记号比大Ω记号更强。对于充分大时为正的 gg,有

f(n)=ω(g(n))⟺f(n)g(n)⟶+∞.f(n)=\omega(g(n)) \quad\Longleftrightarrow\quad \frac{f(n)}{g(n)}\longrightarrow+\infty.

因此,n2=Ω(n2)n^2=\Omega(n^2),但 n2≠ω(n2)n^2\neq\omega(n^2)。相比之下,n2=ω(n)n^2=\omega(n)。

在算法分析中的含义

分析算法时,大Ω记号可以描述任何明确定义的资源函数的下界,常见例子包括时间复杂度和空间复杂度。

设 tA(x)t_A(x) 为算法 AA 在输入 xx 上的运行时间。假定最大值和最小值均存在,定义

Tworst(n)=max⁡∣x∣=ntA(x),Tbest(n)=min⁡∣x∣=ntA(x).T_{\mathrm{worst}}(n)=\max_{|x|=n}t_A(x), \qquad T_{\mathrm{best}}(n)=\min_{|x|=n}t_A(x).

这些函数可以用来表述不同的结论:

  • Tworst(n)=Ω(g(n))T_{\mathrm{worst}}(n)=\Omega(g(n)) 表示,对于每个充分大的输入规模,都存在某个输入,至少需要 c g(n)c\,g(n) 的时间。
  • Tbest(n)=Ω(g(n))T_{\mathrm{best}}(n)=\Omega(g(n)) 表示,对于每个充分大的输入规模,该规模下的每个输入都至少需要 c g(n)c\,g(n) 的时间。
  • 平均情况下界涉及指定输入分布下的期望值。

对于随机化算法,也可以针对算法内部的随机性取期望。期望时间的下界并不自动意味着每次执行都满足同样的下界。

下界并不意味着最好情况复杂度

有时,人们会非正式地将大Ω记号称为“最好情况记号”。这种说法是错误的。最好情况分析和最坏情况分析决定研究的是哪个资源函数;大Ω记号则规定该函数的界的方向。

例如,在未排序的数组(数据结构)中进行顺序查找,可能在第一次比较后就结束。因此,其最好情况运行时间为 Θ(1)\Theta(1)。它的最坏情况运行时间为 Θ(n)\Theta(n),因而也是 Ω(n)\Omega(n)。后一个结论并不意味着每次查找都需要线性时间。

算法下界与问题下界

某个算法的下界不同于整个计算问题的下界。

证明某个特定的排序算法需要 Ω(nlog⁡n)\Omega(n\log n) 的时间,并不能证明所有排序算法都需要这么多时间。问题层面的下界必须涵盖指定计算模型所允许的所有算法。

对 nn 个互不相同的元素进行基于比较的排序时,确定性算法必须区分 n!n! 种可能的输入排列。因此,二叉比较树在最坏情况下的高度至少为

⌈log⁡2(n!)⌉=Ω(nlog⁡n).\left\lceil\log_2(n!)\right\rceil =\Omega(n\log n).

这个下界适用于比较模型。它并不排除在不同假设下采用更快的排序方法,例如利用整数键值范围有界这一特点的方法。归并排序的最坏情况上界为 O(nlog⁡n)O(n\log n),在渐近阶上与比较模型的下界一致。

如何证明大Ω下界

直接利用不等式

最直接的证明方法是给出合适的常数 cc 和 n0n_0。

对于首项系数为正的多项式

p(n)=aknk+ak−1nk−1+⋯+a0,ak>0,p(n)=a_kn^k+a_{k-1}n^{k-1}+\cdots+a_0, \qquad a_k>0,

当 nn 充分大时,所有低次项之和的绝对值至多为 ak2nk\frac{a_k}{2}n^k。因此,对于充分大的 nn,有

p(n)≥ak2nkp(n)\geq \frac{a_k}{2}n^k

由此证明 p(n)=Ω(nk)p(n)=\Omega(n^k)。

比值判别法

如果 g(n)>0g(n)>0 在 nn 充分大时成立,则

f(n)=Ω(g(n))⟺lim inf⁡n→∞f(n)g(n)>0,f(n)=\Omega(g(n)) \quad\Longleftrightarrow\quad \liminf_{n\to\infty}\frac{f(n)}{g(n)}>0,

其中,下极限可以为 +∞+\infty。

特别地,如果比值的通常极限存在且为正,无论是有限正值还是正无穷,都能据此确立大Ω下界。如果极限为零,则该下界不成立。

通常意义下的极限并非必需。例如,

f(n)=n(2+(−1)n)f(n)=n\bigl(2+(-1)^n\bigr)

的比值 f(n)/nf(n)/n 在 11 和 33 之间交替变化。这个比值不收敛,但仍有 f(n)=Ω(n)f(n)=\Omega(n)。

计数与不可避免的工作量

算法下界往往来自所选模型下无法避免的工作,例如读取必需的输入项、显式写出输出,或区分足够多种可能的答案。

这类论证需要精确的假设。在每次操作只能写出常数个输出项的模型中,显式生成 mm 个输出项需要 Ω(m)\Omega(m) 次输出操作。返回压缩表示或指向已有数据的引用属于不同的任务,不一定满足同样的下界。

性质与局限

对于充分大时非负的函数,大Ω关系具有传递性:

f=Ω(g),g=Ω(h)⟹f=Ω(h).f=\Omega(g),\qquad g=\Omega(h) \quad\Longrightarrow\quad f=\Omega(h).

将其中任意一个函数乘以固定的正常数,不会改变这一关系。修改有限多个函数值也不会产生影响。

其渐近性质带来以下局限:

  • 它不给出精确的开销。 诸如 T(n)=Ω(n)T(n)=\Omega(n) 这样的陈述,既不指定具体运行时间,也不指定不等式开始成立的阈值。
  • 它不一定是紧界。 nn 和 n3n^3 都属于 Ω(n)\Omega(n)。
  • 它要求在自变量充分大时有统一的下界。 仅在某个无穷子序列上取大值并不足够。一个在偶数输入上等于 n2n^2、在奇数输入上等于 11 的函数,不属于 Ω(n)\Omega(n)。
  • 它依赖于计算模型。 将任意精度算术运算视为一次操作,与逐一统计比特操作,可能得出不同的界。
  • 它要求明确趋于极限的方式。 当输入有多个参数时,诸如 T(n,m)=Ω(nm)T(n,m)=\Omega(nm) 这样的断言,必须说明涵盖哪些参数取值,以及所用常数是否对这些取值统一适用。

历史上的约定

符号 Ω\Omega 在渐近分析中并非始终具有统一的含义。在解析数论的部分领域所采用的哈代–李特尔伍德约定中,f=Ω(g)f=\Omega(g) 大致表示相对于 gg,ff 在渐近意义下并非可忽略,而不是断言在自变量充分大时存在一个正的下界。

对于正值函数 gg,这一约定通常表述为

lim sup⁡x→∞∣f(x)g(x)∣>0.\limsup_{x\to\infty} \left|\frac{f(x)}{g(x)}\right|>0.

它允许比值仅沿某个子序列保持显著大小,并不要求计算机科学中的不等式对每个充分大的自变量都成立。当自变量充分大时要求下界成立的约定由高德纳倡导,如今已成为算法分析中的标准。因此,在不同数学领域之间切换时,必须核实所采用的定义,而不能仅凭符号推断其含义。