函数的增长

导论的第一章和第二章为基础内容，我的《算法导论》的学习将从算法的复杂性理论分析开始。

渐进记号

本节介绍了一些常见的渐进记号，并介绍了它们的使用方法。

$\Theta$ 记号

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

$\Theta(g(n)) = \left \{f(n)\mid \exist c_1,c_2>0,n_0,s.t.\forall n\ge n_0,0\le c_1g(n)\le f(n)\le c_2g(n)\right \}$

尽管 $\Theta(g(n))$ 是一个集合，我们也可以使用 $f(n) = \Theta(g(n))$ 来表示一个满足条件的 $f(n)$。$f(n)$ 和 $g(n)$ 的关系如下图所示：

换句话说，对所有的 $n\ge n_0$，$f(n)$ 在一个常量因子等于 $g(n)$，我们称 $g(n)$ 是 $f(n)$ 的一个渐进紧确界。既然如此，我们完全可以抛弃这个常量因子，只从高阶项来考虑渐进关系，也就是说，$\Theta$ 记号相当于扔掉低阶项并忽略最高项前的系数。例如：

$\frac{1}{2}n^2-3n=\Theta(n^2)$

接下来我们形式化地用定义证明这个式子，首先先确定 $c_1,c_2,n_0$ 这三个常量，对 $\forall n\ge n_0$，有：

$c_1n^2\le \frac{1}{2}n^2-3n\le c_2n^2$

也就是：

$c_1\le \frac{1}{2}-\frac{3}{n}\le c_2$

只需要选择 $c_1=\frac{1}{14},c_2=\frac{1}{2},n_0=7$ 即可证明。对于其它的例子，有点类似于数学分析中极限的 $\epsilon-N$ 语言，这里不再赘述。

$O$ 记号

前文的 $\Theta$ 记号相当于给出了函数在一个常量因子内的上界和下界，当只有一个渐进上界时，使用 $O$ 记号，也就是说，$O(g(n))$ 是如下的集合：

$O(g(n)) = \left \{f(n)\mid \exist c>0,n_0,s.t.\forall n\ge n_0,0\le f(n)\le cg(n)\right \}$

我们称 $g(n)$ 为 $f(n)$ 的渐进上界。

由定义可知，$\Theta$ 记号是一个比 $O$ 记号更强的概念，用集合论的写法，就是 $\Theta(g(n))\subseteq O(g(n))$。同时，一个 $f(n)$ 可以有很多个渐进上界，例如，我们很容易证明 $f(n)=an+b=O(n)$，也很容易证明 $f(n)=an+b=O(n^2)$，我们在算法复杂度分析中更关注渐进上确界，也就是 $O(n)$。

$O$ 记号太常用了，以至于我们在分析算法的时间复杂度和空间复杂度时，基本都使用 $O$ 记号。由于其代表的时函数的渐进上确界，在多数情况下反映的是算法的最坏情况运行时间和运行空间。例如，插入排序算法的实现中有一个双重嵌套循环，对于特定规模 $n$ 的输入，它的运行时间可能并不能到达 $O(n^2)$ 的量级，但我们说其时间复杂度为 $O(n^2)$，意指对于任意规模 $n$ 的输入，其运行时间的上确界都是 $O(n^2)$。

$\Omega$ 记号

类似于 $O$ 记号，$\Omega$ 记号表示的是算法的渐进下界，也就是如下的集合：

$\Omega(g(n)) = \left \{f(n)\mid \exist c>0,n_0,s.t.\forall n\ge n_0,0\le cg(n)\le f(n)\right \}$

对比着看，$\Omega$ 记号可以用来表达算法最好情况下的运行时间和运行空间度，例如，插入排序的运行时间为 $\Omega(n)$。

关于 $\Theta$ 记号、$O$ 记号和 $\Omega$ 记号，显然有如下定理：

$f(n) = \Theta(g(n)) \Leftrightarrow f(n) = O(g(n)) \text{且} f(n) = \Omega(g(n))$

$o$ 记号

和 $O$ 记号对应，表示 $O(g(n))$ 的集合中不是渐进上确界的那一部分函数。用数学语言说，若 $f(n) = o(g(n))$，则有：

$\lim_{n\to \infty} \frac{f(n)}{g(n)}=0$

$\omega$ 记号

和 $\Omega$ 记号对应，表示 $\Omega(g(n))$ 的集合中不是渐进下确界的那一部分函数。用数学语言说，若 $f(n) = \omega(g(n))$，则有：

$\lim_{n\to \infty} \frac{f(n)}{g(n)}=\infty$

等式和不等式中的渐进记号

渐进符号可以用于数学公式中，例如 $2n^2+3n+1=2n^2+\Theta(n)$，这是因为 $3n+1=\Theta(n)$，这就是虽然 $\Theta(g(n))$ 是一个集合，但是我们仍然使用 $f(n)=\Theta(g(n))$ 而很少使用 $f(n)\in \Theta(g(n))$。

这种表示是有好处的，例如在归并排序中，每一次分治地将一个大的排序问题划分成两个小的排序问题，且两个子问题和原问题的算法是一模一样的。我们用 $T(n)$ 来表示输入规模为 $n$ 的算法的最坏情况运行时间，则根据归并排序的分治过程，我们有如下的递归式：

$T(n) = 2T(n/2)+\Theta(n)$

其中，$2T(n/2)$ 表示两个子问题所需要的时间，$\Theta(n)$ 表示最后的Merge操作，即将两个升序数组合并成一个升序数组的过程，这一部分的时间和问题规模成正比。

渐进记号的性质

渐进记号可以看作两个函数之间的二元关系，它具有自反性、对称性以及传递性，以 $\Theta$ 记号为例：

$\begin{aligned} f(n)=\Theta(g(n)),g(n) &= \Theta(h(n))\Rightarrow f(n) = \Theta(h(n)) \\ f(n) &= \Theta(f(n)) \\ f(n) = \Theta(g(n)) &\Leftrightarrow g(n) = \Theta(f(n)) \end{aligned}$

但是对于 $O$ 记号和 $\Omega$ 记号，对称性要体现在转置上：

$\begin{aligned} f(n) = O(g(n)) \Leftrightarrow g(n) = \Omega(f(n)) \end{aligned}$

练习

3.1-1

不妨设 $h(n) = \max(f(n),g(n))$，这说明 $h(n)\ge f(n)$ 且 $h(n)\ge g(n)$，要证明 $\max(f(n),g(n))=\Theta(f(n)+g(n))$，根据定义，需要选取 $c_1,c_2,n_0$，使得 $\forall n>n_0$，有 $c_1(f(n)+g(n))\le h(n)\le c_2(f(n)+g(n))$，对于右边，由于 $f(n),g(n)$ 均非负，故有 $h(n)\le f(n)+g(n)$，直接取 $c_2=1$ 即可；对于右边，有 $f(n)+g(n)\le h(n)+h(n)=2h(n)$，故直接取 $c_1=\frac{1}{2}$ 即可。

3.1-2

需要选取 $c_1,c_2,n_0$，使得 $c_1n^b\le (n+a)^b\le c_2n^b$，考虑如下极限：

$\lim_{n\to \infty} \frac{(n+a)^b}{n^b}=\lim_{n\to \infty}(1+\frac{a}{n})^b=1$

由极限的定义，取 $\epsilon=\frac{1}{2}$，则$\exist n_0$，当 $n>n_0$ 时，有 $\left | \frac{(n+a)^b}{n^b} -1 \right | <\frac{1}{2}$，即 $\frac{1}{2}< \frac{(n+a)^b}{n^b}<\frac{3}{2}$，即 $\frac{1}{2}n^b\le (n+a)^b\le \frac{3}{2}n^b$，直接取 $c_1=\frac{1}{2},c_2=\frac{3}{2}$ 即可。

3.1-3

显然，因为 $O(n^2)$ 表示的是算法运行时间的上界，表示“最多”是这么多，而不是“至少”是这么多。

3.1-4

$2^{n+1}=2\cdot 2^n=2\cdot O(2^n)=O(2^n)$，但是 $2^{2\cdot 2}=16>4=2^2$，故 $2^{2n}\ne O(2^n)$，事实上，$2^{2n}=\Omega(2^n)$。

3.1-5

这个证明是初等的。必要性显然，充分性只需对 $\Omega$ 记号取 $c_1,n_1$，$O$ 记号取 $c_2,n_2$，最后的 $\Theta$ 记号的三个常数为 $c_1,c_2,\max(n_1,n_2)$ 即可。

3.1-6

这个命题也没什么好讲的，前文已经说明 $O(g(n))$ 和 $\Omega(g(n))$ 在算法分析中的意义。

3.1-7

从两种角度来理解，一个是直观理解：$o(g(n))$ 为除了渐进上确界以外的渐进上界，$\omega(g(n))$ 为除了渐进下确界以外的渐进下界，它们显然没有交集。另一个是从极限角度证明：$f(n)=o(g(n))$ 和 $f(n)=\omega(g(n))$ 的极限定义如下：

$\begin{aligned} \lim_{n\to \infty} \frac{f(n)}{g(n)}&=0 \\ \lim_{n\to \infty} \frac{f(n)}{g(n)}&=\infty \\ \end{aligned}$

这两个式子显然不能同时满足。

3.1-8

类似地定义二元函数，此处略。

3.2-1

这个是高中题了，做差即可。

3.2-2

左边取以 $b$ 为底的对数，得到：

$\log_b(a^{\log_bc})=\log_bc\cdot \log_ba$

右边取以 $b$ 为底的对数，得到：

$\log_b(c^{\log_ba})=\log_ba\cdot \log_bc$

两边是完全一样的。

3.2-3

这里给出两种证明，一种是直接用放缩得到上下界：

$\begin{aligned} \log(n!)&=\sum_{i=1}^n\log i\le\sum_{i=1}^n\log n=n\log n=O(n\log n) \\ \log(n!)&=\log 1+\log 2+\cdots+\log \left \lfloor\frac{n}{2} \right \rfloor+\log (\left \lfloor\frac{n}{2} \right \rfloor+1)+\cdots+\log n \\ &\ge \log(\frac{n}{2})^\frac{n}{2}=\frac{n}{2}\log \frac{n}{2}=\frac{1}{2}n\log n -\frac{\log 2}{2}n=\Omega(n\log n) \end{aligned}$

另一种是直接用斯特林公式：

$\begin{aligned} \log(n!)&=\frac{1}{2}\log(2\pi n)+n\log \frac{n}{e}+\Theta(1) \\ &=\frac{1}{2}\log n+n\log n+\Theta(1) \\ &=\Theta(n\log n) \end{aligned}$

证明第二个命题，直接用放缩配合极限：

$\begin{aligned} \frac{n!}{2^n} \ge \frac{\frac{n}{2}^\frac{n}{2}}{2^n}&=\frac{n^\frac{n}{2}}{2^{\frac{3n}{2}}}=(\frac{n}{8})^\frac{n}{2}\\ \lim_{n\to \infty}(\frac{n}{8})^\frac{n}{2}&=\infty \\ \end{aligned}$

故

$\lim_{n\to \infty}\frac{n!}{2^n}=\infty$

故 $n!=\omega(2^n)$。后半部分仍然考虑极限：

$\lim_{n\to \infty}\frac{n!}{n^n}=\lim_{n\to \infty}\prod_{k=1}^n\frac{k}{n}$

分半考虑，对于前半段，即 $k=1,2,\cdots,\left \lfloor\frac{n}{2} \right \rfloor$ 有：

$\frac{k}{n}\le \frac{1}{2}$

对于后半段，即 $k=\left \lfloor\frac{n}{2} \right \rfloor+1,\cdots,n$ 有：

$0<\frac{k}{n}\le 1$

故

$\prod_{k=1}^n\frac{k}{n} \le \frac{1}{2}^{\left \lfloor\frac{n}{2} \right \rfloor}\to 0$

于是极限

$\lim_{n\to \infty}\frac{n!}{n^n}=\lim_{n\to \infty}\prod_{k=1}^n\frac{k}{n}=0$

故 $n!=o(n^n)$。