函数增长与渐进分析入门

摘要: 函数增长与渐进分析入门

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

在文章 基于随机访问机模型分析算法 中我们了解了算法分析确定算法精确运行时间的方法论。

当输入规模足够大，精确运行时间中的常量和低阶项可以忽略，使得只有增长量级对运行时间有影响，此时需要研究算法的渐进效率，也就是算法运行时间如何随着输入规模的变大而增加。

本文首先定义几个渐进记号，然后总结一下算法分析中常见的函数的行为。

---

渐进记号

$\Theta$ 记号

在文章 基于随机访问机模型分析算法 中我们给出了插入排序最坏情况的运行时间为 $T(n) = an^{2} + bn + c$，此时可以记 $T(n) = \Theta(n^{2})$。

对于给定函数 $g(n)$，$\Theta(g(n))$ 表示以下函数的集合：

$$\Theta(g(n)) = \{f(n): \exists c_{1}, c_{2}, n_{0} > 0, 使得 \forall n \geq n_{0}，有 0 \leq c_{1}g(n) \leq f(n) \leq c_{2}g(n)\}$$

存在正常数 $c_{1}, c_{2}$，使得对足够大的 $n$，函数 $f(n)$ 能夹入 $c_{1}g(n)$ 和 $c_{2}g(n)$ 之间，则 $f(n) \in \Theta(g(n))$，也可以记 $f(n) = \Theta(g(n))$。

下图是 $f(n)$ 与 $g(n)$ 关系的示意图，$f(n) = \Theta(g(n))$ 时，对 $n \geq n_{0}$，$f(n)$ 在一个常量因子内等于 $g(n)$，称 $g(n)$ 为 $f(n)$ 的渐进紧确界。作为对比，$f(n) = O(g(n))$ 为渐进上界，$f(n) = \Omega(g(n))$ 为渐进下界。

一个渐进正函数的低阶项在确定渐进确界时可以忽略，例如 $f(n) = an^{2} + bn + c, a > 0$，去掉低阶项后 $f(n) = \Theta(n^{2})$。令 $c_{1} = \frac{a}{4}, c_{2} = \frac{7a}{4}$，$n_{0} = 2\max(\frac{|b|}{a}, \sqrt{\frac{|c|}{a}})$，可以验证。

$O$ 记号

$\Theta$ 记号渐进地给出了函数的上界和下界，如果只有一个渐进上界，使用 $O$ 记号。对于给定函数 $g(n)$，$O(g(n))$ 表示以下函数的集合：

$$O(g(n)) = \{f(n):\exists c, n_{0}>0，使得 \forall n \geq n_{0}，有 0 \leq f(n) \leq cg(n)\}$$

严格来讲，当记 $f(n) = O(g(n))$ 时，表示 $g(n)$ 的某个常数倍是 $f(n)$ 的渐进上界，但是不要求这个界多么紧，也就是区渐进上界和渐进上确界的区别。

$O$ 记号描述上界，因此常用于描述算法的最坏情况运行时间上界。当我们说运行时间为 $O(n^{2})$ 时，表示存在一个函数 $f(n) \in O(n^{2})$，使得对任意 n，不论选择什么特定的规模为 $n$ 的输入，其运行时间的上界都是 $f(n)$，也就是最坏情况运行时间为 $O(n^{2})$。比如插入排序的最坏情况下的运行时间上界为 $O(n^{2})$。

$\Omega$ 记号

$\Omega$ 记号提供渐进下界，对给定函数 $g(n)$，$\Omega(g(n))$ 表示以下函数的集合：

$$\Omega(g(n)) = \{f(n):\exists c, n_{0}>0，使得 \forall n \geq n_{0}，有 0 \leq cg(n) \leq f(n)\}$$

$\Omega$ 记号描述下界，因此常用于描述算法最好情况运行时间的下界。当我们说运行时间为 $\Omega(g(n))$，其含义是对每个 $n$ 值，不论选择什么特定规模为 $n$ 的输入，只要 n 足够大，其运行时间至少是 $g(n)$ 的常数倍。比如插入排序的最好情况下的运行时间下界为 $\Omega(n)$。

$\Theta(g(n))$、$O(g(n))$、$\Omega(g(n))$ 的关系定理：

定理：
对任意两个函数 $f(n)$, $g(n)$，有 $f(n) = \Theta(g(n))$ 当且仅当 $f(n) = O(g(n))$ 且 $f(n) = \Omega(g(n))$。

证明：

从 $f = \Theta(g(n))$ 出发，我们有：

$$0 \leq c_{1}g(n) \leq f(n) \leq c_{2}g(n) \quad n > n_{0}$$

因此：

$$0 \leq c_{1}g(n) \leq f(n) \quad n > n_{0}S \quad \Rightarrow f(n) = \Omega(g(n)) \\ 0 \leq f(n) \leq c_{2}g(n) \quad n > n_{0}S \quad \Rightarrow f(n) = O(g(n)) \\$$

从 $f(n) = \Omega(g(n)), f(n) = O(g(n))$ 出发，有：

$$0 \leq c_{3}g(n) \leq f(n) \quad n > n_{1}S \\ 0 \leq f(n) \leq c_{4}g(n) \quad n > n_{2}S \\$$

令 $n_{3} = \max(n_{1}, n_{2})$，合并不等式，有：

$$0 \leq c_{3}g(n) \leq f(n) \leq c_{4}g(n) \quad \forall n > n_{3} \quad \Rightarrow f(n) = \Theta(g(n)) \quad \Box$$

渐进记号的解释

（1）当渐进记号独立于等式或不等式右边（即不在一个更大的公式内）时，比如 $n = O(n^{2})$、$n^{2} = \Omega(n)$，此时按照集合的成员关系来解释：$n \in O(n^{2})$、$n^{2} \in \Omega(n)$。

（2）当渐进记号出现在公式中时，比如 $2n^{2} + 3n + 1 = 2n^{2} + \Theta(n)$，此时将其解释为我们不关注名称的匿名函数，$2n^{2} + 3n + 1 = 2n^{2} + f(n)$，$f(n) \in \Theta(n)$。

按照以上解释方法，归并排序的最坏情况运行时间可以表示为递归式：

$$T(n) = 2T(\frac{n}{2}) + \Theta(n)$$

如果只对 $T(n)$ 的渐进行为感兴趣，则没必要准确说明低阶项，它们都被包含在 $\Theta(n)$ 表示的匿名函数中。

（3）当渐进记号出现在等式左边时，比如 $2n^{2} + \Theta(n) = \Theta(n^{2})$，此时的解释方法为：无论怎样选择等号左边的匿名函数，总有一种办法选择等号右边的匿名函数使得等式成立。对任意函数 $f(n) \in \Theta(n)$，存在 $g(n) \in \Theta(n^{2})$，使得对所有 $n$ 有 $2n^{2} + f(n) = g(n)$。也就是说右边比左边提供的细节更粗糙。

$o$ 记号

$O$ 记号提供的渐进上界可能是也可能不是渐进紧确的，比如 $2n^{2} \in O(n^{2})$ 是渐进紧确的，但 $2n = O(n^{2})$ 不是。

我们用 $o$ 记号表示非渐近紧确上界，$o(g(n))$ 定义为以下集合：

$$o(g(n)) = \{f(n): \forall c > 0, \exists n_{0} > 0, 使得 \forall n \geq n_{0}, 有 0 \leq f(n) < cg(n)\}$$

$O$ 记号与 $o$ 记号的直观对比：

• $f(n) = O(g(n))$ 中，界 $0 \leq f(n) \leq cg(n)$ 对某个常数 $c > 0$ 成立。
• $f(n) = o(g(n))$ 中，界 $0 \leq f(n) < cg(n)$ 对所有常数 $c > 0$ 成立。

$2n = o(n^{2})$ 但 $2n^{2} \neq o(n^{2})$。若 $f(n) = o(g(n))$，则有 $\lim\limits_{n\rightarrow\infty}\frac{f(n)}{g(n)} = 0$，这里涉及无穷小/无穷大的阶，在算法分析中，匿名函数还限定是渐进非负的。

$\omega$ 记号

$\omega$ 记号表示非渐近紧下界，$\omega(g(n))$ 定义为以下集合：

$$\omega(g(n)) = \{f(n): \forall c > 0, \exists n_{0} > 0, 使得 \forall n \geq n_{0}, 有 0 \geq cg(n) < f(n)\}$$

$\omega$ 记号与 $\Omega$ 记号的关系类似于 $o$ 记号于 $O$ 记号的关系。如下：

$$f(n) \in \omega(g(n)) \Leftrightarrow g(n) \in o(f(n))$$

$2n^{2} = \omega(n)$ 但 $2n^{2} \neq \omega(n^{2})$。$f(n) \in \omega(g(n))$ 隐含着 $\lim\limits_{n\rightarrow\infty}\frac{f(n)}{g(n)} = \infty$。

---

渐进记号的性质

假定 $f(n)$ 和 $g(n)$ 渐进为正。

传递性

$$f(n) = \Theta(g(n)) 且 g(n) = \Theta(h(n)) \Rightarrow f(n) = \Theta(h(n)) \\ f(n) = O(g(n)) 且 g(n) = O(h(n)) \Rightarrow f(n) = O(h(n)) \\ f(n) = \Omega(g(n)) 且 g(n) = \Omega(h(n)) \Rightarrow f(n) = \Omega(h(n)) \\ f(n) = o(g(n)) 且 g(n) = o(h(n)) \Rightarrow f(n) = o(h(n)) \\ f(n) = \omega(g(n)) 且 g(n) = \omega(h(n)) \Rightarrow f(n) = \omega(h(n)) \\$$

自反性

$$f(n) = \Theta(f(n)) \\ f(n) = O(f(n)) \\ f(n) = \Omega(f(n)) \\$$

对称性

$$f(n) = \Theta(g(n)) \Leftrightarrow g(n) = \Theta(f(n))$$

转置对称性

$$f(n) = O(g(n)) \Leftrightarrow g(n) = \Omega(f(n)) \\ f(n) = o(g(n)) \Leftrightarrow g(n) = \omega(f(n)) \\$$

两个函数的渐进比较

两个函数的渐进比较与两个实数的比较，可以做如下类比：

两个函数的渐进比较	两个实数的比较
$f(n) = O(g(n))$	$a \leq b$
$f(n) = \Omega(g(n))$	$a \geq b$
$f(n) = \Theta(g(n))$	$a = b$
$f(n) = o(g(n))$	$a < b$
$f(n) = \omega(g(n))$	$a > b$

$f(n) = o(g(n))$，可以称 $f(n)$ 渐进小于 $g(n)$；$f(n) = \omega(g(n))$，可以称 $f(n)$ 渐进大于 $g(n)$。

三分性

对任意两个实数 a 和 b，以下三种情况必有一个成立：$a < b, a = b, a > b$。

但注意，这个性质渐进记号不具备。也就是说对于两个函数 $f(n)$ 和 $g(n)$，$f(n) = O(g(n))$ 和 $f(n) = \Omega(g(n))$ 都不成立。比如 $f(n) = n$，$g(n) = n^{1 + \sin{n}}$。

---

算法分析常用函数

上取整、下取整

对实数 $x$，$\left\lfloor x\right\rfloor$ 为下取整函数，表示小于等于 $x$ 的最大整数；$\left\lceil x\right\rceil$ 为上取整函数，表示大于等于 $x$ 的最小整数。

下面是一些取整函数的结论：

$$\forall x, \quad x - 1 < \left\lfloor x\right\rfloor \leq x \leq \left\lceil x\right\rceil < x + 1$$ $$\forall n, \quad \left\lceil \frac{n}{2}\right\rceil + \left\lfloor \frac{n}{2}\right\rfloor = n$$

$\forall x \geq 0, a, b > 0$ 有：

$$\left\lceil \frac{\left\lceil x/a\right\rceil}{b}\right\rceil = \left\lceil \frac{x}{ab}\right\rceil \\ \left\lfloor \frac{\left\lfloor x/a\right\rfloor}{b}\right\rfloor = \left\lfloor \frac{x}{ab}\right\rfloor \\ \left\lceil \frac{a}{b}\right\rceil \leq \frac{a + (b - 1)}{b} \\ \left\lfloor \frac{a}{b}\right\rfloor \geq \frac{a - (b - 1)}{b} \\$$

模运算

对 $\forall a \in \mathbb{Z}, n \in \mathbb{Z^{+}}$，$a \mod n$ 就是商 $\frac{a}{n}$ 的余数：

$$a \mod n = a - n \left\lfloor \frac{a}{n}\right\rfloor$$

a 与 b 模 n 同余：$a \equiv b \mod n$，当且仅当 $n$ 是 $b - a$ 的一个因子。

多项式

给定非负整数 $d$，$n$ 的 $d$ 次多项式是以下形式：

$$p(n) = \sum\limits_{i=0}\limits^{d}a_{i}n^{i}$$

其中 $a_{i}$ 为多项式系数，且 $a_{d} \neq 0$。$p(n)$ 是渐进的当且仅当 $a_{d} > 0$，且 $p(n) = \Theta(n^{d})$。

若 $f(n) = O(n^{k})$，称 $f(n)$ 多项式有界。

指数

对 $a > 1$ 的实数常量 $a$, $b$，有 $\lim\limits_{n\rightarrow\infty}\frac{n^{b}}{a^{n}} = 0$，也就是 $n^{b} = o(a^{n})$。

对数

弱队某个常数 k，$f(n) = O(\log^{k}n)$，则称函数 $f(n)$ 时多对数有界的。

对于常量 $a > 0$，$\log^{b}n = o(n^{a})$，也就是 $\lim\limits_{n\rightarrow\infty}\frac{\log^{b}n}{n^{a}} = 0$。

阶乘

斯特林公式给出了阶乘的渐进紧确界：

$$n! = \sqrt{2\pi n}(\frac{n}{e})^{n}(1 + \Theta(\frac{1}{n}))$$

由以上斯特林公式，可以推出以下结论：

$$\log(n!) = \Theta(n\log n) \\ n! = o(n^{n}) \\ n! = \omega(2^{n}) \\$$

下面分别给出推导过程：

$$\begin{align} \log(n!) &= \log(\sqrt{2\pi n}(\frac{n}{e})^{n}(1 + \Theta(\frac{1}{n}))) \\ &= \log\sqrt{2\pi n} + \log(\frac{n}{e})^{n} + \log(1 + \Theta(\frac{1}{n})) \\ &= \Theta(\log{n}) + n\log{\frac{n}{e}} + \log(\Theta(1) + \Theta(\frac{1}{n})) \\ &= \Theta(\log{n}) + \Theta(n\log n) + \Theta(\frac{1}{n}) \\ &= \Theta(n\log n) \end{align}$$ $$\begin{align} \lim\limits_{n\rightarrow\infty}\frac{n^{n}}{n!} &= \lim\limits_{n\rightarrow\infty}\frac{n^{n}}{\sqrt{2\pi n}(\frac{n}{e})^{n}(1 + \Theta(\frac{1}{n}))} \\ &= \lim\limits_{n\rightarrow\infty}\frac{e^{n}}{\sqrt{2\pi n}(1 + \Theta(\frac{1}{n}))} \\ &= \lim\limits_{n\rightarrow\infty}O(\frac{1}{\sqrt{n}})e^{n} \\ &\geq \lim\limits_{n\rightarrow\infty}\frac{e^{n}}{c\sqrt{n}} \quad\quad (c > 0)\\ &\geq \lim\limits_{n\rightarrow\infty}\frac{e^{n}}{cn} \\ &= \lim\limits_{n\rightarrow\infty}\frac{e^{n}}{c} = \infty \end{align}$$ $$\begin{align} \lim\limits_{n\rightarrow\infty}\frac{2^{n}}{n!} &= \lim\limits_{n\rightarrow\infty}\frac{2^{n}}{\sqrt{2\pi n}(\frac{n}{e})^{n}(1 + \Theta(\frac{1}{n}))} \\ &= \lim\limits_{n\rightarrow\infty}\frac{1}{\sqrt{2\pi n}(1 + \Theta(\frac{1}{n}))}(\frac{2e}{n})^{n} \\ &\leq \lim\limits_{n\rightarrow\infty}(\frac{2e}{n})^{n} \\ &\leq \lim\limits_{n\rightarrow\infty}\frac{1}{2^{n}} = 0 \quad\quad (n > 4e) \end{align}$$

多重函数

用记号 $f^{(i)}(n)$ 表示函数 $f(n)$ 重复 i 次作用于一个初值 n 上。$f(n)$ 为实数集上的一个函数，对非负整数 i，递归定义：

$$f^{(i)}(n) = \left\{ \begin{array}{**lr**} \begin{align} & n & i = 0 \\ & f(f^{(i-1)}(n)) & i > 0 \\ \end{align} \end{array} \right.$$

多重对数函数

$\log^{(i)}n$ 为前面的多重函数定义下，$f(n) = \log n$ 时的函数，注意这里需要 $\log^{(i-1)}n > 0$。于是我们可以给出多重对数函数 $\log^{*}n$ 的定义：

$$\log^{* }n = \min\{i \geq 0: \log^{(i)}n \leq 1\}$$

这是一个增长非常缓慢的函数。

---