算法设计-01：导论

斐波那契数列

评价一个算法，始终围绕三个问题：它正确吗？它跑多快（作为输入规模 $n$ 的函数）？我们能不能做得更好？本讲用斐波那契数列贯穿始终，回答这三个问题。其形式化定义：

斐波那契在《计算之书》（Liber Abaci）中推动了十进制记数法在欧洲的传播；讲义随后用以他命名的数列比较不同算法的效率。

$$F_n = \begin{cases} 0 & n = 0 \\ 1 & n = 1 \\ F_{n-1} + F_{n-2} & n > 1 \end{cases}$$

指数时间算法 FIBO1：照定义递归实现。

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：FIBO1}(n) \\[4pt] \hline \textbf{输入：}\ \text{自然数 } n \\ \textbf{if}\ n = 0\ \textbf{then}\ \text{return}(0) \\ \textbf{if}\ n = 1\ \textbf{then}\ \text{return}(1) \\ \text{return}\ \text{FIBO1}(n-1) + \text{FIBO1}(n-2) \\ \hline \end{array}&& \end{aligned}$$

FIBO1 把定义直接翻译成递归——$F_n$ 分解为 $F_{n-1}$ 与 $F_{n-2}$ 两个子问题分别求解再相加，正确性显然。但每次求 $F_n$ 都要重新计算两个子问题，子问题又被更深层递归重复计算，形成海量冗余。设 $T(n)$ 为 FIBO1$(n)$ 的计算机步数：

$$T(n) = O(1)\ (n \le 1), \qquad T(n) = T(n-1) + T(n-2) + 3\ (n > 1)$$

递推式与斐波那契同构，可归纳证明 $T(n) \ge F_n$，故 $T(n)$ 随 $n$ 指数增长。

例如 $F_6=8$，但 FIBO1$(6)$ 会重复计算 FIBO1$(4)$、FIBO1$(3)$ 等子问题。讲义提出的 $F_{100}$ 和 $F_{200}$ 分别为 $354224848179261915075$ 和 $280571172992510140037611932413038677189525$；前者有 69 位，后者有 138 位。结果本身并不长，耗时主要来自重复递归。

指数增长的代价仍然惊人。$F_{200}=280571172992510140037611932413038677189525\approx2.81\times10^{41}$，介于 $2^{137}$ 与 $2^{138}$ 之间。按讲义采用的 2010 年“天河一号”约 $2.57\times10^{15}$ 步/秒估算，仅执行 $F_{200}$ 次基本操作就至少需要约 $1.1\times10^{26}$ 秒，即 $3.5\times10^{18}$ 年。课件在这一页给出的 $2^{138}$ 与十进制近似值不一致，笔记采用精确数值重新估算。按摩尔定律硬件每 18 个月翻番，而 FIBO1 耗时正比于 $2^{0.694n}\approx1.6^n$：算 $F_{n+1}$ 比 $F_n$ 约慢 $1.6$ 倍，即硬件每年约只能多承担一个输入下标。这是指数时间的代价。

多项式时间算法 FIBO2：自底向上填表，消除重复计算。

$$\begin{aligned} &\begin{array}{l} \hline \textbf{算法：FIBO2}(n) \\[4pt] \hline \textbf{输入：}\ \text{自然数 } n \\ \textbf{if}\ n = 0\ \textbf{then}\ \text{return}(0) \\ \text{创建数组 } f[0 \dots n] \\ f[0] = 0;\ f[1] = 1 \\ \textbf{for}\ i = 2\ \textbf{to}\ n\ \textbf{do} \\ \quad f[i] = f[i-1] + f[i-2] \\ \text{return}\ f[n] \\ \hline \end{array}&& \end{aligned}$$

FIBO2 按 $i = 2, 3, \dots, n$ 依次计算 $f[i]$，每个值只依赖前两项且只算一次，消除了指数级重复。内层循环执行 $n-1$ 次，故步数关于 $n$ 线性，从指数级降至多项式级。

更细致地看：若加法为常数时间（32 位整数），FIBO2 为 $O(n)$。但第 $n$ 个斐波那契数约 $0.694n$ 位，大数加法需正比于位数的代价（见第二讲）。任意精度加法下，第 $i$ 轮花 $O(i)$ 位操作，故 FIBO2 实际为 $\sum_{i=1}^{n}O(i)=O(n^2)$，仍为多项式。FIBO1 的加法次数已是指数级；即使用 $O(n)$ 作为每次加法的统一上界，总时间仍至多为 $O(nF_n)$，并至少与调用次数同阶。

渐近记号

渐近记号刻画函数的增长趋势，忽略常数因子与低阶项。

大 O 记号（上界）：

定义（大 O）：$f(n)$ 是 $O(g(n))$，若存在常数 $c > 0$ 与 $n_0 \ge 0$，使对所有 $n \ge n_0$ 有 $0 \le f(n) \le c \cdot g(n)$。

$O(g(n))$ 是"增长不超过 $g(n)$"的函数集合；$c$ 负责放大常数，$n_0$ 决定从足够大处观察。例：$f(n) = 32n^2 + 17n + 1$ 是 $O(n^2)$（取 $c = 50, n_0 = 1$），但不是 $O(n)$ 也不是 $O(n \log n)$。典型用法：插入排序需 $O(n^2)$ 次比较。

Quiz：$f(n)=3n^2+17n\log n+1000$ 是 $O(n^2)$、$O(n^3)$，还是两者都是？

两者都是。因为 $n\log n=O(n^2)$，整个式子是 $O(n^2)$；又因 $n^2=O(n^3)$，它也是 $O(n^3)$。其中 $O(n^2)$ 给出的上界更紧。

记号滥用：严格地 $f(n) \in O(g(n))$，但习惯写 $f(n) = O(g(n))$。等号是单向的——$g_1 = 5n^3$、$g_2 = 3n^2$ 均有 $g_1 = O(n^3)$、$g_2 = O(n^3)$，却不能推出 $g_1 = g_2$。

大 O 记号的性质：自反性（$f = O(f)$）、常数因子（$f = O(g) \Rightarrow cf = O(g)$）、乘积（$f_1 = O(g_1), f_2 = O(g_2) \Rightarrow f_1 f_2 = O(g_1 g_2)$）、求和（$f_1 + f_2 = O(\max\{g_1, g_2\})$）、传递性（$f = O(g), g = O(h) \Rightarrow f = O(h)$）。

乘积性质的证明：由定义存在 $c_1, n_1$ 使 $0 \le f_1(n) \le c_1 g_1(n)$（$n \ge n_1$），存在 $c_2, n_2$ 使 $0 \le f_2(n) \le c_2 g_2(n)$（$n \ge n_2$）。两式相乘得 $0 \le f_1 f_2 \le c_1 c_2 g_1 g_2$（$n \ge \max\{n_1, n_2\}$），恰为乘积定义。由此 $f(n) = 5n^3 + 3n^2 + n + 1234$ 是 $O(n^3)$——最高次项主导。

大 Ω 记号（下界）：

定义（大 Ω）：$f(n)$ 是 $\Omega(g(n))$，若存在常数 $c > 0$ 与 $n_0 \ge 0$，使对所有 $n \ge n_0$ 有 $f(n) \ge c \cdot g(n) \ge 0$。

$\Omega$ 与 $O$ 方向相反，等价关系：$f = \Omega(g)$ 当且仅当 $g = O(f)$。例：$f(n) = 32n^2 + 17n + 1$ 既是 $\Omega(n^2)$ 也是 $\Omega(n)$，但不是 $\Omega(n^3)$。典型用法：任何基于比较的排序算法最坏情况至少需 $\Omega(n \log n)$ 次比较。

Quiz：$f=\Omega(g)$ 是否等价于 $g=O(f)$？若 $f(n)\ge cg(n)$ 只对无穷多个 $n$ 成立，是否足够？

第一种说法成立，把不等式两边交换即可得到相同的定义。第二种说法不成立：$\Omega$ 要求从某个 $n_0$ 开始对所有更大的 $n$ 成立。例如令 $g(n)=n$，$f(n)$ 在偶数 $n$ 时为 $n$、奇数 $n$ 时为 $1$；前者对无穷多个 $n$ 成立，但 $f\notin\Omega(g)$。

大 Θ 记号（紧界）：

定义（大 Θ）：$f(n)$ 是 $\Theta(g(n))$，若存在常数 $c_1 > 0, c_2 > 0$ 与 $n_0 \ge 0$，使对所有 $n \ge n_0$ 有 $0 \le c_1 g(n) \le f(n) \le c_2 g(n)$。

$\Theta$ 同时夹紧上下界，等价于 $f = O(g)$ 且 $f = \Omega(g)$。例：$f(n) = 32n^2 + 17n + 1$ 是 $\Theta(n^2)$，但不是 $\Theta(n^3)$ 也不是 $\Theta(n)$。典型用法：归并排序需 $\Theta(n \log n)$ 次比较。

Quiz：$f=\Theta(g)$ 是否等价于 $f$ 同时是 $O(g)$ 和 $\Omega(g)$？是否等价于 $f(n)/g(n)$ 收敛到一个正的有限常数？

第一种说法成立。第二种只给出充分条件，并非必要条件：取 $g(n)=n$，$f(n)=n(2+(-1)^n)$，则 $n\le f(n)\le3n$，所以 $f=\Theta(g)$；但比值在 $1$ 与 $3$ 之间交替，没有极限。

渐近界与极限：极限是判断渐近关系的捷径。

命题：若 $\lim_{n \to \infty} \frac{f(n)}{g(n)} = c$ 且 $0 < c < \infty$，则 $f(n)$ 是 $\Theta(g(n))$。

证明：由极限定义，对任意 $\varepsilon > 0$，存在 $n_0$ 使 $c - \varepsilon \le \frac{f(n)}{g(n)} \le c + \varepsilon$（$n \ge n_0$）。取 $\varepsilon = \frac{c}{2} > 0$，两边乘 $g(n)$ 得 $\frac{c}{2}g(n) \le f(n) \le \frac{3c}{2}g(n)$，正是 $\Theta$ 定义（$c_1 = \frac{c}{2}$、$c_2 = \frac{3c}{2}$）。思路是"夹逼"：极限收敛到 $c$，就把比值锁在 $c$ 附近，从而把 $f$ 夹在两个常数倍的 $g$ 之间。

补充命题：若极限为 $0$，则 $f = O(g)$ 但非 $\Omega(g)$；若极限为 $\infty$，则 $f = \Omega(g)$ 但非 $O(g)$。

常见函数的渐近界

利用极限判别，可得常见函数的渐近界：

• 多项式：$f(n) = a_0 + a_1 n + \cdots + a_d n^d$（$a_d > 0$）是 $\Theta(n^d)$，因 $\lim_{n\to\infty} \frac{f(n)}{n^d} = a_d > 0$。
• 对数与多项式：任意 $a > 1, d > 0$，$\log_a n$ 是 $O(n^d)$，因 $\lim_{n\to\infty} \frac{\log_a n}{n^d} = 0$。
• 指数与多项式：任意 $r > 1, d > 0$，$n^d$ 是 $O(r^n)$，因 $\lim_{n\to\infty} \frac{n^d}{r^n} = 0$。
• 阶乘：$n!$ 是 $2^{\Theta(n \log n)}$，由斯特林公式 $n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n$ 可证。

增长快慢层次（慢→快）：$\log n \prec n^d\,(d>0) \prec r^n\,(r>1) \prec n!$。

练习 0.1：对下列每组函数，判断 $f=O(g)$、$f=\Omega(g)$，还是两者都成立（即 $f=\Theta(g)$）。

考查渐近记号的极限判别，以及对数、多项式、指数和阶乘的增长速度。以下均令 $n\to\infty$；$f/g$ 趋于 $0$、正的有限常数或 $\infty$ 时，分别得到 $O(g)$、$\Theta(g)$ 或 $\Omega(g)$。

(a) $f(n)=n-100$，$g(n)=n-200$。

$\dfrac{f(n)}{g(n)}=\dfrac{1-100/n}{1-200/n}\to1$，故 $f=\Theta(g)$。

(b) $f(n)=n^{1/2}$，$g(n)=n^{2/3}$。

$\dfrac{f(n)}{g(n)}=n^{-1/6}\to0$，故 $f=O(g)$。

© $f(n)=100n+\log n$，$g(n)=n+(\log n)^2$。

两边主项都是线性项，$\dfrac{f(n)}{g(n)}\to100$，故 $f=\Theta(g)$。

(d) $f(n)=n\log n$，$g(n)=10n\log(10n)$。

由 $\log(10n)=\log n+\log10$，有 $\dfrac{f(n)}{g(n)}\to1/10$，故 $f=\Theta(g)$。

(e) $f(n)=\log(2n)$，$g(n)=\log(3n)$。

$\dfrac{f(n)}{g(n)}=\dfrac{\log n+\log2}{\log n+\log3}\to1$，故 $f=\Theta(g)$。

(f) $f(n)=10\log n$，$g(n)=\log(n^2)$。

$g(n)=2\log n$，故 $\dfrac{f(n)}{g(n)}=5$，即 $f=\Theta(g)$。

(g) $f(n)=n^{1.01}$，$g(n)=n(\log n)^2$。

$\dfrac{f(n)}{g(n)}=\dfrac{n^{0.01}}{(\log n)^2}\to\infty$，故 $f=\Omega(g)$。

(h) $f(n)=n^2/\log n$，$g(n)=n(\log n)^2$。

$\dfrac{f(n)}{g(n)}=\dfrac{n}{(\log n)^3}\to\infty$，故 $f=\Omega(g)$。

(i) $f(n)=n^{0.1}$，$g(n)=(\log n)^{10}$。

正数次幂快于任意固定的对数幂，$\dfrac{f(n)}{g(n)}\to\infty$，故 $f=\Omega(g)$。

(j) $f(n)=(\log n)^{\log n}$，$g(n)=n/\log n$。

$\ln(f/g)=(\log n)\ln\log n-\ln n+\ln\log n\to\infty$，故 $f=\Omega(g)$。

(k) $f(n)=\sqrt n$，$g(n)=(\log n)^3$。

$\dfrac{f(n)}{g(n)}\to\infty$，故 $f=\Omega(g)$。

(l) $f(n)=n^{1/2}$，$g(n)=5^{\log_2 n}$。

$g(n)=n^{\log_2 5}$ 且 $\log_2 5>1/2$，故 $f=O(g)$。

(m) $f(n)=n2^n$，$g(n)=3^n$。

$\dfrac{f(n)}{g(n)}=n(2/3)^n\to0$，故 $f=O(g)$。

(n) $f(n)=2^n$，$g(n)=2^{n+1}$。

$\dfrac{f(n)}{g(n)}=1/2$，故 $f=\Theta(g)$。

(o) $f(n)=n!$，$g(n)=2^n$。

$n!\ge(n/2)^{\lfloor n/2\rfloor}$，所以 $\dfrac{f(n)}{g(n)}\to\infty$，故 $f=\Omega(g)$。

(p) $f(n)=(\log n)^{\log n}$，$g(n)=2^{(\log_2 n)^2}$。

$\ln f=\Theta(\log n\log\log n)$，而 $\ln g=\Theta((\log n)^2)$；故 $f/g\to0$，即 $f=O(g)$。

(q) $f(n)=\sum_{i=1}^{n}i^k$，$g(n)=n^{k+1}$，其中 $k$ 是固定的非负整数。

由积分比较，

$$\frac{n^{k+1}}{k+1} \le\sum_{i=1}^{n}i^k \le\frac{(n+1)^{k+1}-1}{k+1}.$$

两端除以 $n^{k+1}$ 得 $\dfrac{f(n)}{g(n)}\to\dfrac1{k+1}$，故 $f=\Theta(g)$。

练习 0.2：设 $c>0$，证明几何和 $g(n)=1+c+c^2+\cdots+c^n$ 分别满足以下渐近界。

考查等比数列求和与渐近上下界。

(a) 当 $c<1$ 时，证明 $g(n)=\Theta(1)$。

$1\le g(n)=\dfrac{1-c^{n+1}}{1-c}\le\dfrac1{1-c}$，故 $g(n)=\Theta(1)$。

(b) 当 $c=1$ 时，证明 $g(n)=\Theta(n)$。

$g(n)=n+1=\Theta(n)$。

© 当 $c>1$ 时，证明 $g(n)=\Theta(c^n)$。

$c^n\le g(n)=\dfrac{c^{n+1}-1}{c-1}\le\dfrac{c}{c-1}c^n$，故 $g(n)=\Theta(c^n)$。

多变量大 O：算法常有多个输入参数，如节点数 $n$ 与边数 $m$。

定义（多变量大 O）：$f(m, n)$ 是 $O(g(m, n))$，若存在常数 $c > 0, m_0 \ge 0, n_0 \ge 0$，使对所有 $n \ge n_0$、$m \ge m_0$ 有 $f(m, n) \le c \cdot g(m, n)$。

例：$f(m, n) = 32mn^2 + 17mn + 32n^3$ 是 $O(mn^2 + n^3)$ 与 $O(mn^3)$，但不是 $O(n^3)$ 也不是 $O(mn^2)$。典型用法：BFS 在 $n$ 节点、$m$ 边的有向图求最短路径耗时 $O(m + n)$。