非紧渐近符号

算法的时间复杂度

在了解接下来的非紧渐近符号之前, 我们先来思考如何用一般(紧)渐近符号描述一个算法的时间复杂度.

$\Theta$ 的充要条件定理

我们以一个定理来引入, 即渐近符号的夹逼定理, 或者更正式的称为:

Theta 的充要条件定理 (Theorem on the equivalence of $\Theta$ and the combination of $O$ and $\Omega$)

如下: 对于两个正函数 $f(n)$ 和 $g(n)$, 有: $$f(n)=\Theta (g(n))\text{当且仅当}f(n)=O(g(n))\text{且}f(n)=\Omega (g(n))$$

这个定理说明了 Big-Theta 符号是 Big-O 和 Big-Omega 的“交集”. 其证明也非常的简单, 可以通过分别证明充分性和必要性解决. 通过前面的学习, 完成它应该不是什么大问题, 故本书不再赘述.

通过这个定义, 我们可以更好的了解算法的时间复杂度是怎么表示的. 在之前我们已经聊过这个问题了, 现在再深入地解决一下:

• 所有的符号都并非只是描述算法的一种情况, 我们一般给出三种情况: 最坏, 最优(好)和一般¹, 在无特定规定下, 符号描述可以参照脚注2².
• $O(g(n))$ 表示在对应情况下, 算法的时间复杂度不超过 $g(n)$ 的常数倍.
• $\Omega (g(n))$ 表示在对应情况下, 算法的时间复杂度至少为 $g(n)$ 的常数倍.
• $\Theta (g(n))$ 表示在对应情况下, 算法的时间复杂度总在 $g(n)$ 的两个常数倍之间.
• 以上三个表达都只是简单描述, 任何需要专业化的表达, 最好参照前面的定义进行.

$o$ 符号

接下来, 我们来看今天的主题——非紧渐近符号: 非紧渐近符号们提供了 非紧界(Non-tight bounds). 它们有时也被称为 严格渐近符号(Strict asymptotic notation) 或 小记号(Little notations)³.

我们来看 $o$ 符号的定义: $$o(g(n))=\{f(n)|\forall c>0,\exists n_0\in \mathbb{N},\forall n\ge n_0:|f(n)|<c\cdot |g(n)|\}$$

与 $O$ 主要区别在于: 在 $f(n)=O(g(n))$ 中, 界 $0\le f(n)\le cg(n)$ 对某个常量 $c>0$ 成立, 在 $f(n)=o(g(n))$ 中, 界 $0\le f(n)<cg(n)$ 对所有常量 $c>0$ 成立. 这也就是说, 在 $o$ 记号中, 当 $n$ 趋向于无穷大时, $f(n)$ 对于 $g(n)$ 就微不足道了, 即: $$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=0$$

关于非紧界这个描述, 是因为 $O$ 包含同阶函数而 $o$ 反之. 如, $f(n)=O(n)$ 但 $f(n)\ne o(n)$. 同理, 可以推出 $f(n)=o(g(n))\Rightarrow f(n)=O(g(n))$. 在本章节的练习与回答中, 也可以通过这种方法判断正误.

$\omega$ 符号

不严谨地说, 它与 $o$ 符号相反. 我们可以利用 $o$ 来定义它, 下面这个定义同样是它的一个性质: $$f(n)\in w(g(n))\text{当且仅当}g(n)\in o(f(n))$$

形式化的定义是: $$\omega (g(n))=\{f(n)|\forall c>0,\exists n_0\in \mathbb{N},\forall n\ge n_0:|f(n)|>c\cdot |g(n)|\}$$

同样地, 我们有 $f(n)=\omega (g(n))\Rightarrow f(n)=\Omega (g(n))$. 例如, $n^2=\omega (n)$ 但 $n^2\ne \omega (n^2)$ 不过 $n^2=\Omega (n^2)$.

同时还要注意, 我们使用的是 $\Rightarrow$, 这意味着关于 Big-O 和 little-o, Big-Omega 和 little-omega 上面这两个结论都不可逆.

另外我们同样有个极限表达: $$\underset{n\to \infty }{\lim }\frac{f(n)}{g(n)}=\infty$$

相关比较性质

就像$a<b$这样, 可以把渐近符号之间的比较与实数之间的比较形象类比在一起. 上面在遵照本书之前定义的同时, 默认函数在足够大时取非负值:

在深入定义之前, 我们可以将渐近记号与实数的大小关系对应起来, 这有助于记忆:

我们主要关注五个性质:自反性、对称性、传递性、转置对称性和三分性(三歧性).

如果关系 $\sim$ 满足: 对任意函数 $f(n)$, 都有 $f(n)\sim f(n)$⁴, 则称该关系具有自反性.

• $\Theta$ (Theta): 自反
• $f(n)=\Theta (f(n))$ 恒成立. 就像 $a=a$.
• $O$ (Big-O): 自反
• $f(n)=O(f(n))$ 恒成立. 就像 $a\le a$.
• $\Omega$ (Big-Omega): 自反
• $f(n)=\Omega (f(n))$ 恒成立. 就像 $a\ge a$.
• $o$ (Little-o): 非自反
• $f(n)\ne o(f(n))$. 因为 $f(n)$ 不能严格小于它自己. 就像 $a<a$ 不成立.
• $\omega$ (Little-omega): 非自反
• $f(n)\ne \omega (f(n))$. 因为 $f(n)$ 不能严格大于它自己. 就像 $a>a$ 不成立.

如果关系 $\sim$ 满足: $f(n)\sim g(n)$ 推导出 $g(n)\sim f(n)$, 则称该关系具有对称性.

• $\Theta$ (Theta): 对称
• 若 $f(n)=\Theta (g(n))$, 则 $g(n)=\Theta (f(n))$. 就像 $a=b$ 推导 $b=a$.
• $O$ (Big-O): 非对称
• $n=O(n^2)$ 成立, 但 $n^2\ne O(n)$. 就像 $a\le b$ 不能推导 $b\le a$.
• $\Omega$ (Big-Omega): 非对称
• $n^2=\Omega (n)$ 成立, 但 $n\ne \Omega (n^2)$.
• $o$ (Little-o): 非对称
• 若 $f(n)=o(g(n))$, 则 $g(n)\ne o(f(n))$.
• $\omega$ (Little-omega): 非对称
• 若 $f(n)=\omega (g(n))$, 则 $g(n)\ne \omega (f(n))$.

如果关系 $\sim$ 满足: $f(n)\sim g(n)$ 且 $g(n)\sim h(n)$ 推导出 $f(n)\sim h(n)$, 则称该关系具有传递性.

• 所有记号 ($\Theta ,O,\Omega ,o,\omega$) 均具有传递性
• 例如: 若 $f=O(g)$ 且 $g=O(h)$, 则 $f=O(h)$.
• 这与实数性质一致: 若 $a\le b$ 且 $b\le c$, 则 $a\le c$.

下面是渐近记号特有的性质, 指两个关系互为“逆”关系.

定义: 若 $f(n)\sim g(n)$ 推导出 $g(n)\approx f(n)$ (其中 $\approx$ 是 $\sim$ 的对应逆关系), 则称它们具有转置对称性.

• $O$ 与 $\Omega$ 互为转置对称
• $f(n)=O(g(n))⟺g(n)=\Omega (f(n))$
• 类比: $a\le b⟺b\ge a$
• $o$ 与 $\omega$ 互为转置对称
• $f(n)=o(g(n))⟺g(n)=\omega (f(n))$
• 类比: $a<b⟺b>a$
• $\Theta$ 是自身的转置对称
• $f(n)=\Theta (g(n))⟺g(n)=\Theta (f(n))$
• 这也解释了为什么 $\Theta$ 具有对称性.

对于任意两个函数 $f(n)$ 和 $g(n)$, 必须且只能满足以下三种关系之一:

1. $f(n)=o(g(n))$ (小于)
2. $f(n)=\Theta (g(n))$ (等于)
3. $f(n)=\omega (g(n))$ (大于)

• 结论: 渐近记号满足三分性 (针对 $o,\Theta ,\omega$ 的组合).
• 注意: 这里的三分性是指 $o,\Theta ,\omega$ 这三个关系构成了完整的划分. 对于任意两个渐近非负函数 $f$ 和 $g$, 它们必然处于这三种关系中的一种.
• 这类似于实数的三分律: 对于任意 $a,b$, 必有 $a<b$、$a=b$ 或 $a>b$.
• 陷阱提示: $O$ 和 $\Omega$ 不满足三分性.
• 例如: $f(n)=n$, $g(n)=n^2$.
• 我们有 $f=O(g)$ 成立, 但 $f=\Omega (g)$ 不成立.
• 同时, $g=\Omega (f)$ 成立, 但 $g=O(f)$ 不成立.
• 但是, 如果我们考虑 $O$ 和 $\Omega$ 的组合, 情况会变得复杂 (因为 $O$ 和 $\Omega$ 可以同时成立, 即 $\Theta$). 真正的“互斥且穷尽”的三分关系是由 $o$、$\Theta$、$\omega$ 构成的.

根据上述性质, 我们可以将这些记号分类:

1. 等价关系:

• 只有 $\Theta$ 是等价关系.
• 因为它满足自反性、对称性和传递性.
• 这意味着 $\Theta$ 将函数集合划分成了若干个等价类 (例如所有的多项式函数 $n^2,2n^2+1,0.5n^2$ 都属于同一个等价类 $\Theta (n^2)$).

2. 偏序关系:

• $O$ 和 $\Omega$ 是偏序关系.
• 因为它们满足自反性、反对称性 (注意: 这里的反对称性指如果 $f=O(g)$ 且 $f=\Omega (g)$, 则 $f=\Theta (g)$) 和传递性.
• 它们描述了一种“大小”顺序, 但不要求任意两个元素都可比 (虽然在算法分析中常遇到的函数通常可比, 但数学上存在不可比的函数, 如震荡函数).

3. 严格偏序关系:

• $o$ 和 $\omega$ 是严格偏序关系.
• 因为它们满足传递性和非自反性(irreflexive).
• 它们描述了严格的“大小”关系, 不允许相等.

练习与回答

1. 判断下列关于 Big-O 和 little-o 的陈述是否正确.
   • $3n^2+5n=O(n^2)$
   • $3n^2+5n=o(n^2)$
   • $\sqrt{n}=o(n)$
   • $\log n=O(n)$
   • $\log n=o(n)$

$3n^2+5n=o(n^2)$ 错误, 正确的应该是 $3n^2+5n=O(n^2)$ 或 $3n^2+5n=o(n^3)$. 其余四个均正确.

2. 根据已知内容, 判断下列关于 Big-Omega 和 little-omega 陈述是否正确.

已知:

• 若 ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=\infty$, 则 $f(n)=\omega (g(n))$
• 若 ${\lim }_{n\to \infty }\frac{f(n)}{g(n)}=c>0$, 则 $f(n)=\Theta (g(n))\subseteq \Omega (g(n))$, 但不是 $\omega$

则判断:

• $f(n)=n^3$, $g(n)=n^2$ 是否满足 $f(n)=\omega (g(n))$
• $f(n)=5n\log n$, $g(n)=4n\log n$ 是否满足 $f(n)=\omega (g(n))$
• $f(n)=n\log n$, $g(n)=n$ 是否满足 $f(n)=\omega (g(n))$ 又满足 $f(n)=\Omega (g(n))$

对于上面已知内容, 可以在下一节具体学习. 以上除第2题以外都正确, 通过极限法证明即可.

3. 假设 $f(n)$ 与 $g(n)$ 都是渐近非负函数. 使用 $\Theta$ 记号的基本定义来证明 $\max (f(n),g(n))=\Theta (f(n)+g(n))$.

证明:

根据 $\Theta$ 记号的定义, 需要证明存在正常数 $c_1,c_2,n_0$, 使得对所有 $n\ge n_0$, 有: $$c_1(f(n)+g(n))\le \max (f(n),g(n))\le c_2(f(n)+g(n))$$

(1)证明上界:

显然, $\max (f(n),g(n))\le f(n)+g(n)$

因为 $\max (f(n),g(n))$ 要么等于 $f(n)$, 要么等于 $g(n)$, 无论哪种情况都不超过两者之和.

取 $c_2=1$.

(2)证明下界:

不失一般性, 假设 $\max (f(n),g(n))=f(n)$(另一种情况对称)

则 $f(n)\ge g(n)\ge 0$

因此: $$f(n)+g(n)\le f(n)+f(n)=2f(n)=2\max (f(n),g(n))$$

即: $$\max (f(n),g(n))\ge \frac{1}{2}(f(n)+g(n))$$

取 $c_1=\frac{1}{2}$.

结论: 存在 $c_1=\frac{1}{2},c_2=1$, 使得对充分大的 $n$: $$\frac{1}{2}(f(n)+g(n))\le \max (f(n),g(n))\le (f(n)+g(n))$$

因此 $\max (f(n),g(n))=\Theta (f(n)+g(n))$.

1. 事实上为: 最坏情况(Worst-case)、最好情况(Best-case)、平均情况(Average-case)、摊还情况(Amortized). ↩

2. 对于算法的最坏情况, 一般使用$O$；对于算法的平均情况, 一般使用$\Theta$；对于算法的最好情况, 一般使用$\Omega$. ↩

3. $o$(little-o) 是 $O$(Big-O) 的小记号. $\omega$(little-omega) 是 $\Omega$(Big-Omega) 的小记号. ↩

4. 这里省略了匿名函数. ↩