算法分析的数学基础

阅读前提示

• 本文理论来源为机械工业出版社的《算法导论》第三版教材．
• 本文主要从函数增长的角度概述算法分析过程中所需要的数学基础．
• 若存在错误或表达不规范之处，请通过邮箱联系加以指正．

各类渐近记号

各类渐近记号的定义如下表所示．

记号	定义	称法
$\Theta$ 记号	$f(n)=\Theta(g(n))\Leftrightarrow\exists\,c _1,\,c _2,\,n _0>0,\,\forall\,n\geqslant n _0,\,0\leqslant c _1g(n)\leqslant f(n)\leqslant c _2g(n)$	$g(n)$ 是 $f(n)$ 的一个渐近紧确界
$O$ 记号	$f(n)=O(g(n))\Leftrightarrow\exists\,c,\,n _0>0,\,\forall\,n\geqslant n _0,\,0\leqslant f(n)\leqslant cg(n)$	$g(n)$ 是 $f(n)$ 的一个渐近上界
$\Omega$ 记号	$f(n)=\Omega(g(n))\Leftrightarrow\exists\,c,\,n _0>0,\,\forall\,n\geqslant n _0,\,0\leqslant cg(n)\leqslant f(n)$	$g(n)$ 是 $f(n)$ 的一个渐近下界
$o$ 记号	$f(n)=o(g(n))\Leftrightarrow\forall\,c>0,\,\exists\,n _0>0,\,\forall\,n\geqslant n _0,\,0\leqslant f(n)<cg(n)$	$g(n)$ 是 $f(n)$ 的一个非渐近紧确的上界
$\omega$ 记号	$f(n)=\omega(g(n))\Leftrightarrow\forall\,c>0,\,\exists\,n _0>0,\,\forall\,n\geqslant n _0,\,0\leqslant cg(n)<f(n)$	$g(n)$ 是 $f(n)$ 的一个非渐近紧确的下界

注意事项

部分教材所给出的渐近记号的定义方法可能有所不同，但本质上是一致的，如：

1. $f(n)=\Theta(g(n))$ 可描述为 $\Theta(g(n))=\{\,f(n)\,|\,\exists\,c _1,\,c _2,\,n _0>0,\,\forall\,n\geqslant n _0,\,0\leqslant c _1g(n)\leqslant f(n)\leqslant c _2g(n)\,\}$，其余记号同理；
2. $f(n)=o(g(n))$ 可定义为 $\lim\limits _{n\to\infty}\dfrac{f(n)}{g(n)}=0$；
3. $f(n)=\omega(g(n))$ 可定义为 $\lim\limits _{n\to\infty}\dfrac{f(n)}{g(n)}=\infty$；
4. $f(n)=\omega(g(n))$ 当且仅当 $g(n)\in o(f(n))$．

渐近记号的性质如下所示．

1. 传递性：$\{\,f(n)=\mathcal{S}(g(n))\,\}\wedge\{\,g(n)=\mathcal{S}(h(n))\,\}\rightarrow\{\,f(n)=\mathcal{S}(h(n))\,\}$，其中 $\mathcal{S}$ 表示同种渐近记号．
2. 自反性：$f(n)=\mathcal{S}(f(n))$，其中 $\mathcal{S}$ 表示 $\Theta$ 记号、$O$ 记号或 $\Omega$ 记号．
3. 对称性：$f(n)=\Theta(g(n))\Leftrightarrow g(n)=\Theta(f(n))$．
4. 转置对称性：$f(n)=O(g(n))\Leftrightarrow g(n)=\Omega(f(n))$，$f(n)=o(g(n))\Leftrightarrow g(n)=\omega(f(n))$．
5. 界限性：$\{\,f(n)=O(g(n))\,\}\wedge\{\,f(x)=\Omega(g(n))\,\}\Leftrightarrow\{\,f(x)=\Theta(g(x))\,\}$．

为方便记忆，可借用高等数学中“阶”的定义描述渐近关系，并将其与实数关系进行类比，如下表所示．

渐近关系	阶描述	实数关系
$f(n)=\Theta(g(n))$	$f(n)$ 是 $g(n)$ 的同阶函数	$a=b$
$f(n)=O(g(n))$	$f(n)$ 是 $g(n)$ 的低阶函数	$a\leqslant b$
$f(n)=\Omega(g(n))$	$f(n)$ 是 $g(n)$ 的高阶函数	$a\geqslant b$
$f(n)=o(g(n))$	$f(n)$ 是 $g(n)$ 的严格低阶函数	$a<b$
$f(n)=\omega(g(n))$	$f(n)$ 是 $g(n)$ 的严格高阶函数	$a>b$

渐近关系的计算与证明

常用定理

我们主要关注不太常见的定理，如调和级数上界的计算，其形式为

$\displaystyle H _n=\sum\limits _{i=1}^n\dfrac{1}{i}=\ln n+O(1)$

基础证明

例题

设 $\displaystyle p(n)=\sum\limits _{i=0}^da _in^i$，其中 $a _d>0$，试证明 $p(n)=\Theta(n^d)$．

证明：由于

$$ p(n)\leqslant(d+1)\max\limits _{i=0,\,1,\,\cdots,\,d}a _i\cdot n^d=O(n^d) $$

且

$$ p(n)\geqslant a_dn^d=\Omega(n^d) $$

故 $p(n)=\Theta(n^d)$，证毕．

批注

若 $f(n)=O(n^k)$，则称 $f(n)$ 是多项式有界的．

例题

试证明 $\displaystyle\sum\limits _{i=1}^n\Theta(f(i))=\Theta\left(\,\sum\limits _{i=1}^nf(i)\right)$．

证明：此处采用数学归纳法，即

1. 当 $n=1$ 时，$\Theta(f(1))=\Theta(f(1))$ 显然成立；

2. 假设当 $n=k$ 时结论成立，即有 $\displaystyle\sum\limits _{i=1}^k\Theta(f(i))=\Theta\left(\,\sum\limits _{i=1}^kf(i)\right)$ 成立；

3. 当 $n=k+1$ 时，有 $$ \begin{aligned} \sum\limits _{i=1}^{k+1}\Theta(f(i))&=\sum\limits _{i=1}^k\Theta(f(i))+\Theta(f(k+1))\\\\ &=\Theta\left(\,\sum\limits _{i=1}^kf(i)\right)+\Theta(f(k+1))\\\\ &=\Theta\left(\,\sum\limits _{i=1}^kf(i)+f(k+1)\right)\\\\ &=\Theta\left(\,\sum\limits _{i=1}^{k+1}f(i)\right) \end{aligned} $$ 结论同样成立；

4. 故对于任意正整数 $n$，都有 $\displaystyle\sum\limits _{i=1}^n\Theta(f(i))=\Theta\left(\,\sum\limits _{i=1}^nf(i)\right)$ 成立，证毕．

界的求解

例题

设在数列 $\{a _n\}$ 中恒有 $\dfrac{a _{i+1}}{a _i}\leqslant r<1$ 成立，试求 $\displaystyle\sum\limits _{i=0}^na _i$ 的一个上界．

解：由于

$$ \begin{cases} \dfrac{a _1}{a _0}\leqslant r\Rightarrow a _1\leqslant a _0r \\\\ \dfrac{a _2}{a _1}\leqslant r\Rightarrow a _2\leqslant a _1r\leqslant a _0r^2 \\\\ \cdots \\\\ \dfrac{a _i}{a _{i-1}}\leqslant r\Rightarrow a _i\leqslant a _{i-1}r\leqslant\cdots\leqslant a _0r^i \end{cases} $$

故 $\displaystyle\sum\limits _{i=0}^na _i\leqslant\sum\limits _{i=0}^\infty a _0r^i=a _0\sum\limits _{i=0}^\infty r^i=\dfrac{a _0}{1-r}$，即 $\dfrac{a _0}{1-r}$ 是 $\displaystyle\sum\limits _{i=0}^na _i$ 的一个上界．

例题

试求 $\displaystyle\sum\limits _{i=0}^\infty\dfrac{i^2}{2^i}$ 的一个上界．

解：当 $k\geqslant 3$ 时，有 $\dfrac{\left[\,\dfrac{(k+1)^2}{2^{k+1}}\,\right]}{\left[\,\dfrac{k^2}{2^k}\,\right]}=\dfrac{(k+1)^2}{2k^2}\leqslant\dfrac{8}{9}$ 成立，则

$$ \begin{aligned} \displaystyle\sum\limits _{i=0}^\infty\dfrac{i^2}{2^i}&=\sum\limits _{i=0}^2\dfrac{i^2}{2^i}+\sum\limits _{i=3}^\infty\dfrac{i^2}{2^i}\\\\ &\leqslant\Theta(1)+\dfrac{9}{8}\cdot\sum\limits _{i=3}^\infty\left(\dfrac{8}{9}\right)^i\\\\ &=O(1) \end{aligned} $$

例题

试求 $\displaystyle H _n=\sum\limits _{i=1}^n\dfrac{1}{i}$ 的上界．

解：直接展开可得

$$ \begin{aligned} \displaystyle H _n=\sum\limits _{i=1}^n\dfrac{1}{i}&=\dfrac{1}{1}+\left(\dfrac{1}{2}+\dfrac{1}{3}\right)+\left(\dfrac{1}{4}+\dfrac{1}{5}+\dfrac{1}{7}+\dfrac{1}{8}\right)+\left(\dfrac{1}{8}+\dfrac{1}{9}+\cdots+\dfrac{1}{15}\right)+\cdots\\\\ &\leqslant\dfrac{1}{1}+\left(\dfrac{1}{2}+\dfrac{1}{2}\right)+\left(\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{4}+\dfrac{1}{4}\right)+\left(\dfrac{1}{8}+\dfrac{1}{8}+\cdots+\dfrac{1}{8}\right)+\cdots\\\\ &=\dfrac{1}{1}+\dfrac{1}{2}\times 2+\dfrac{1}{4}\times 4+\cdots\\\\ &=\sum\limits _{i=1}^{\lceil\,\lg n\,\rceil} 1\\\\ &\leqslant\lg n+1\\\\ &=O(\lg n) \end{aligned} $$

主定理

设有常数 $a\geqslant 1$ 和 $b>1$，$f(n)$ 是一个函数，$T(n)$ 是定义在非负整数集上的函数，其形式为

$$ T(n)=aT\left(\dfrac{n}{b}\right)+f(n) $$

则有：

1. 若 $f(n)=O(n^{\log _ba-\varepsilon})$，其中 $\varepsilon>0$，则 $T(n)=\Theta(n^{\log _ba})$；
2. 若 $f(n)=\Theta(n^{\log _ba})$，则 $T(n)=\Theta(n^{\log _ba}\lg n)$；
3. 若 $f(n)=\Omega(n^{\log _ba+\varepsilon})$，其中 $\varepsilon>0$，且对于任意充分大的 $n$ 与常数 $c>1$，均有 $af\left(\dfrac{n}{b}\right)\leqslant cf(n)$ 成立，则 $T(n)=\Theta(f(n))$．

注意事项

当 $f(n)$ 与 $n^{\log _ba}$ 不同阶时，只有令其满足多项式差的关系，即存在常数 $\varepsilon>0$，使得

$$ f(n)=O\left(\dfrac{n^{\log _ba}}{n^\varepsilon}\right) $$

或

$$ f(n)=\Omega(n^{\log _ba}\cdot n^\varepsilon) $$

成立时，才能使用主定理．

就直观视觉而言，我们在使用主定理进行计算时，需要做的事情其实是比较 $f(n)$ 与 $n^{\log _ba}$ 的大小：

1. 若 $f(n)=n^{log _ba}$，则 $T(n)=\Theta(n^{\log _ba}\lg n)=\Theta(f(n)\lg n)$；
2. 若 $f(n)\neq n^{\log _ba}$，则 $T(n)=\Theta(\max(f(n),\,n^{\log _ba}))$．