思考与提高

最高阶项决定一切

我们发现最高阶项决定一切, 从而将一个函数转化为关于 $Θ$ 渐近形式, 这在直觉上是对的.

像上面这样, 在本书中我们多次提到 最高阶项决定一切, 大部分情况下它是正确的. 但需要更严谨的表述. “最高阶项决定一切” 这种表述很显然是基于多项式, 事实上它在多项式条件下确实是对的.

也就是说: 对于实系数多项式, 其渐近行为由最高次项决定. 严格的定理如下:

定理

设 $f (n) = a_{k} n^{k} + a_{k - 1} n^{k - 1} + \dots + a_{0}, a_{k} \neq = 0$ 则当 $n \to \infty$ 时, $f (n) \sim a_{k} n^{k} 即 n \to \infty lim \frac{f ( n )}{a _{k} n ^{k}} = 1$

$\frac{f ( n )}{a _{k} n ^{k}} = \frac{a _{k} n ^{k} + a _{k - 1} n ^{k - 1} + \dots + a _{0}}{a _{k} n ^{k}} = 1 + \frac{a _{k - 1}}{a _{k}} \cdot \frac{1}{n} + \frac{a _{k - 2}}{a _{k}} \cdot \frac{1}{n ^{2}} + \dots + \frac{a _{0}}{a _{k}} \cdot \frac{1}{n ^{k}}$

当 $n \to \infty$ , 所有 $\frac{1}{n ^{j}} \to 0$ ( $j \geq 1$ ), 所以:

$n \to \infty lim \frac{f ( n )}{a _{k} n ^{k}} = 1$

即 $f (n) \sim a_{k} n^{k}$

由此可得:

$f (n) = Θ (n^{k})$
$f (n) = O (n^{k})$
$f (n) = Ω (n^{k})$

该证明相当简单, 且与直觉相符, 是一种显而易见的证明.

但数学中的函数并不只有这些, 我们还有一些常见的函数, 例如指数函数, 沿用上述证明,进一步推广也是有效的. 也就是说对于指数函数, 我们同样有最高阶项决定一切这样的表述.

然而有一些函数不满足我们上面的这个表述, 常见的是非加性结构: $T (n) = 2 T (n /2) + n$ , 这种结构不能靠上面的方法直接证明, 相反,我们需要下一章将学到的主定理等工具. 这里暂时不做讨论. 另外振荡或交替项也很难探讨, 如 $f (n) = n + (- 1)^{n} n$ , 它们不收敛, 在极限讨论的时候, 主导行为也相当复杂. 另外, 对数函数和 $e^{n}$ 这些不同函数混合的情况, 也要进行单独考虑.

主导项

事实上, 在渐近分析中, 真正重要的是 主导项(dominant term), 即随着 $n \to \infty$ , 其占比趋于 1 的项.

若函数可写为和式: $f (n) = f_{1} (n) + f_{2} (n) + \dots + f_{m} (n)$ 且存在某个 $f_{i} (n)$ ,使得对所有 $j \neq = i$ , $n \to \infty lim \frac{f _{j} ( n )}{f _{i} ( n )} = 0$ 则称 $f_{i} (n)$ 为主导项,且 $f (n) \sim f_{i} (n), 即 f (n) = (1 + o (1)) f_{i} (n)$

这就是 “主导项决定渐近行为” 的一般原则.

在渐近分析中,“最高次项决定一切” 是一个常见但需要谨慎理解的说法.它在许多情况下是成立的,尤其对于多项式函数或具有主导项的函数,但在更一般的情形下需要附加条件.

常见练习

证明 $f (n) = Θ (g (n))$ 当且仅当 $f (n) = O (g (n))$ 且 $f (n) = Ω (g (n))$ .

证明:

(必要性 $\Rightarrow$ ): 假设 $f (n) = Θ (g (n))$

由定义, 存在正常数 $c_{1}, c_{2}, n_{0}$ , 使得对所有 $n \geq n_{0}$ : $c_{1} g (n) \leq f (n) \leq c_{2} g (n)$

从右边不等式 $f (n) \leq c_{2} g (n)$ , 得 $f (n) = O (g (n))$
从左边不等式 $c_{1} g (n) \leq f (n)$ , 得 $f (n) = Ω (g (n))$

(充分性 $\Leftarrow$ ): 假设 $f (n) = O (g (n))$ 且 $f (n) = Ω (g (n))$

由 $f (n) = O (g (n))$ , 存在 $c_{2}, n_{1} > 0$ , 使得对 $n \geq n_{1}$ : $f (n) \leq c_{2} g (n)$
由 $f (n) = Ω (g (n))$ , 存在 $c_{1}, n_{2} > 0$ , 使得对 $n \geq n_{2}$ : $f (n) \geq c_{1} g (n)$

取 $n_{0} = max (n_{1}, n_{2})$ , 则对所有 $n \geq n_{0}$ : $c_{1} g (n) \leq f (n) \leq c_{2} g (n)$

因此 $f (n) = Θ (g (n))$ .

证明 $o (g (n)) \cap ω (g (n))$ 为空集.

证明(反证法):

假设存在函数 $f (n) \in o (g (n)) \cap ω (g (n))$ .

由 $f (n) \in o (g (n))$ : 对任意常数 $c > 0$ , 存在 $n_{1}$ , 使得对所有 $n \geq n_{1}$ : $f (n) < c \cdot g (n)$

特别地, 对 $c = 1$ , 存在 $n_{1}$ 使得 $f (n) < g (n)$ .

由 $f (n) \in ω (g (n))$ : 对任意常数 $c > 0$ , 存在 $n_{2}$ , 使得对所有 $n \geq n_{2}$ : $f (n) > c \cdot g (n)$

特别地, 对 $c = 1$ , 存在 $n_{2}$ 使得 $f (n) > g (n)$ .

矛盾: 取 $n_{0} = max (n_{1}, n_{2})$ , 则对 $n \geq n_{0}$ : $f (n) < g (n) 且 f (n) > g (n)$

结论: $o (g (n)) \cap ω (g (n)) = \emptyset$ .

拓展记号

试拓展记号 $O$ , $Θ$ , $Ω$ , 使之对 $g (n, m)$ (其中 $n$ , $m$ 以不同速率趋向于 $\infty$ )有效.

解答:

对于二元函数, 我们需要明确两个变量如何趋向无穷. 有以下几种方式:

方式1: 同时趋向无穷

$f (n, m) = O (g (n, m))$ 表示存在正常数 $c, n_{0}, m_{0}$ , 使得对所有 $n \geq n_{0}$ 且 $m \geq m_{0}$ : $f (n, m) \leq c \cdot g (n, m)$

类似地定义 $Ω$ 和 $Θ$ .

方式2: 一个变量固定, 另一个趋向无穷

$f (n, m) = O_{n} (g (n, m))$ : 对每个固定的 $m$ , $f$ 关于 $n$ 是 $O (g)$
$f (n, m) = O_{m} (g (n, m))$ : 对每个固定的 $n$ , $f$ 关于 $m$ 是 $O (g)$

方式3: 指定增长路径

当 $n, m$ 以特定关系趋向无穷时(如 $m = n^{2}$ ), 沿该路径定义渐近记号.

示例:

$f (n, m) = n^{2} + m^{2} = Θ (n^{2} + m^{2})$
$f (n, m) = nm = O (n^{2} m^{2})$
若 $m = O (n)$ , 则 $nm = O (n^{2})$

实际应用: 在算法分析中, 常用于分析具有多个输入参数的算法复杂度.

Keyboard shortcuts

算法学习