《算法导论》渐近记号

作者: Sun东辉 | 来源:发表于2022-06-08 10:30 被阅读0次

$\Theta$ 记号

定义

对一个给定的函数 g(n)，用 $\Theta$ (g(n))来表示函数集合： $\Theta(g(n))$ = { $f(n)$ ：存在正常量 $c_1、c_2$ 和 $n_0$ 使得对所有 $n \geq n_0$ ，有 $0 \leq c_1g(n)\leq f(n)\leq c_2g(n)$ }。

解释

对任一个函数 f(n)，若存在正常数 $c_1$ ， $c_2$ ，使当 n 充分大时，f(n) 能被夹在 $c_1g(n)$ 和 $c_2g(n)$ 中间，则 f(n) 属于集合 $\Theta(g(n))$ 。因为 $\Theta(g(n))$ 是一个集合，可以写成 “ $f(n)\in\Theta(g(n))$ ”，表示 f(n) 是 $\Theta(g(n))$ 的元素。不过，通常写成 “ $f(n)=\Theta(g(n))$ ”来表示相同的意思。

上图给出函数 f(n) 与 g(n) 的直观图示，其中 f(n) = $\Theta(g(n))$ 。对于所有位于 $n_0$ 右边的 n 值，f(n) 的值落在 $c_1g(n)$ 和 $c_2g(n)$ 之间，换句话说，对所有的 n≥ $n_0$ ，f(n) 在一个常因子范围内与 g(n) 相等。我们说 g(n) 是 f(n) 的一个渐近确界。

$\Theta(g(n))$ 的定义需要每个成员 $f(n)\in\Theta(g(n))$ 都是渐近非负，也就是说当 n 足够大时 f(n) 是非负值（渐近正函数则是当 n 足够大时总为正值）。这就要求函数 g(n) 本身也必须是渐近非负的，否则集合 $\Theta(g(n))$ 就是空集。因此，假定 $\Theta$ 记号中用到的每个函数都是渐近非负的。

例子：

例 1：证明 $\frac{1}{2}n^2-3n=\Theta(n^2)$ 。

首先要确定常数 $c_1$ ， $c_2$ 和 $n_0$ ，使得对所有的 n≥ $n_0$ ，即

$c_1n^2\leq\frac12n^2-3n\leq c_2n^2$

成立，用 $n^2$ 除不等式得

$c_1\leq\frac12-\frac3n\leq c_2$

右边的不等式在 $c_2\geq\frac{1}{2}$ 时对所有的 $n\geq1$ 成立。同样，左边的不等式可以让 $c_1\leq\frac{1}{14}$ 时对所有的 $n\geq7$ 成立。这样，通过选择 $c_1=\frac{1}{14}$ ， $c_2=\frac{1}{2}$ ，以及 $n_0=7$ ，可以证明 $\frac{1}{2}n^2-3n=\Theta(n^2)$ 。当然，还存在其他的常数选择，而重要的是确实存在某个选择。需要注意的是，这些常数依赖于函数 $\frac{1}{2}n^2-3n$ ， $\Theta(n^2)$ 中不同的函数通常需要不同的常数。

例 2: 证明 $6n^2$ ≠ $\Theta(n^2)$ 。

使用反证法进行证明，假设存在常数 $c_2$ 和 $n_0$ ，使对所有的 $n\geq n_0$ ，有 $6n^3\leq c_2n^2$ ；这样就有 $n\leq \frac{c_2}{6}$ ，这对于任意大的 n 是不可能成立的，因为 $c_2$ 是常数。

例 3: 任意的二次函数 $f(n)=an^2+bn+c$ ，其中 a，b 和 c 都是常数，且 $a > 0$ 。

舍掉低阶项并忽略常数项得出 $f(n)=\Theta(n^2)$ 。可以发现，当常数 $c_1=\frac{a}{4}$ ， $c_2=\frac{7a}{4}$ 且 $n_0=a\times max(\frac{\vert b\vert}a,\sqrt{\frac{\vert c\vert}a})$ ，时，对于所有的 $n\geq n_0$ ，满足 $0\leq c_1n^2 \leq an^2+bn+c \leq c_2n^2$ 。

O 记号

定义：

$\Theta$ 记号渐近地给出了一个函数的上界和下界。当只有一个渐近上界时，使用 O 记号。对于给定函数 g(n)，用 O(g(n))（读作“大 Og(n)”，有时仅读作”Og(n)”）来表示以下函数的集合：O(g(n))={f(n): 存在正常量 c 和 $n_0$ ，使得对所有 n≥ $n_0$ ，有 0≤f(n)≤cg(n)}

解释

上图说明了 O 记号的直观意义，对位于 $n_0$ 右边的 n 值，函数 f(n) 的值在 g(n) 之下。
利用 O 记号，我们常常能通过查看算法的总体结构来描述算法的运行时间。例如，插入排序算法中的二重循环结构立即能引出其最坏情况运行的上界 $O(n^2)$ ，内循环每一轮迭代的代价以 $O(n^0)$ （常量 $O(1)$ ）为上界，下标 i 和 j 最大可以取到 n，对于 $n^2$ 个 i 值和 j 值对中的每一对，内循环至多执行一次。

$\Omega$ 记号

定义

正如 O 记号提供了一个函数的渐近上界， $\Omega$ 记号提供了渐近下界。对于给定的函数 g(n)，用 $\Omega(g(n))$ (读作“大 $\Omega g(n)$ ”，有时仅读作“ $\Omega g(n)$ ”)来表示以下函数的集合： $\Omega g(n)$ = {f(n)：存在正常量 c 和 $n_0$ ，使得对所有 n≥ $n_0$ ，有 0≤cg(n)≤f(n)}

解释

上图说明了

\Omega

记号的直观意义，对所有在

n_0

右边的 n 值，函数 f(n) 的数值等于或大于 cg(n)。

o 记号

O 记号与 o 记号的定义是类似的，主要区别在于对 f(n)=O(g(n))，界 0≤ f(n)≤ cg(n) 对某个常数 c>0 成立，但对 f(n)=o(g(n))，界 0≤ f(n)≤ cg(n) 对所有常数 c>0 成立。从直觉上看，在 o 表示中当 n 趋于无穷时，函数 f(n) 相对于 g(n) 来说就不重要了，即
$\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}\;=\;0$

$\omega$ 记号

定义

表示非渐近紧确的下界，它的一种定义为 $f(n)\in \omega(g(n))$ ，当且仅当 $g(n)\in o(f(n))$ 。 $\omega(g(n))$ 的形式定义为集合 $\omega(g(n))=f(n)$ ，对任意正常数 c>0，存在常数 $n_0>0$ ，有 $0\leq cg(n)<f(n)$ 。
例如： $\frac{n^2}{2}=\omega(n)$ ，但 $\frac{n^2}{2}$ ≠ $\omega(n^2)$ 。关系 f(n)= $\omega(g(n))$ 意味着
$\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}\;=\;\infty$
如何这个极限存在。也就是说当 n 趋于无穷时，f(n) 相对 g(n) 来说变得任意大了。

一个例子

设 $p(n)=\sum_{i=0}^da_in^i$ 为一个 n 的 d 次多项式，其中 $a_d > 0$ ，令 k 为一个常数。利用渐近记号的定义来证明如下性质：
1. 若 k≥d，则 $p(n)=O(n^k)$ 。
2. 若 k≤d，则 $p(n)=\Omega(n^k)$ 。
3. 若 k=d，则 $p(n)=\Theta(n^k)$ 。
4. 若 k>d，则 $p(n)=o(n^k)$ 。
5. 若 k<d，则 $p(n)=\omega(n^k)$ 。