程序 = 数据结构 + 算法
计算机科学并不只是关于计算机，就像天文学并不只关于望远镜一样。—— Edsger Dijkstra
参考资料：点击此处
算法的基本概念
算法是对特定问题求解的一种描述，是指令的有限序列。
| 算法 | |
|---|---|
| 特点 | 有穷性、确定性、可行性、输入、输出。 |
| 正确算法 | 对于每一个输入都最终停止，而且产生了正确的输出 |
| 不正确算法 | 在某个输入上不停止；对所有输入都停止但对某输入产生不正确的结构 |
| 近似算法 | 对所有输入都停止 |
| 复杂度 | 时间复杂度：基本运算（原子操作）的执行次数；空间复杂度：算法所需存储空间的大小 |
| 基本运算 | 解决给定问题时占支配地位的运算。讨论一个算法的优劣通常只考虑基本运算 |
算法分析的数学基础
| 记号 | 含义 |
|---|---|
| $\lfloor x \rfloor$ | 小于等于 $x$ 的最大整数 |
| $\lceil x \rceil$ | 大于等于 $x$ 的最小整数 |
| $\log n$ | $\log n = \log_{2} n$ |
| $\ln n$ | $\ln n = \log_{\mathrm{e}} n$ |
复杂性函数的阶
渐进复杂性
当输入规模 $n$ 趋近于极限时的复杂性
| 复杂性函数 | 定义 |
|---|---|
| $$T(n) = \varOmega(f(n))$$ | 如果存在 $c>0$ 与正整数 $n_0 \leqslant 1$，当 $n \geqslant n_0$ 时，都有 $T(n) \geqslant c \cdot f(n)$ 成立，则称 $T(n)$ 是 $f(n)$ 的高阶，它给出了算法复杂度的下界 |
| $$T(n) = O(f(n))$$ | 如果存在 $c>0$ 与正整数 $n_0 \leqslant 1$，当 $n \geqslant n_0$ 时，都有 $T(n) \leqslant c \cdot f(n)$ 成立，则称 $T(n)$ 是 $f(n)$ 的低阶，它给出了算法复杂度的上界 |
| $$T(n) = \varTheta(f(n))$$ | 如果存在 $c_1, c_2 > 0$ 与正整数 $n_0 \leqslant 1$，当 $n \geqslant n_0$ 时，都有 $c_2 f(n) \leqslant T(n) \leqslant c_1 f(n)$ 恒成立，则称 $T(n)$ 与 $f(n)$ 同阶 |
| 严格低阶函数集合 | $o(g(n)) = \{ f(n) | 对任意 c>0，都存在正整数 n_0，使得当 n>n_0 时都有 0 \leqslant f(n) \leqslant c \cdot g(n) \}$ |
| 严格高阶函数集合 | $\omega(g(n)) = \{ f(n) | 对任意 c>0，都存在正整数 n_0，使得当 n>n_0 时都有 0 \leqslant c \cdot g(n) \leqslant f(n) \}$ |
| 严格上界 | 若 $f(n) \in o(g(n))$，称 $g(n)$ 是 $f(n)$ 的严格上界，记作 $f(n) = o(g(n))$ |
| 严格下界 | 若 $f(n) \in \omega(g(n))$，称 $g(n)$ 是 $f(n)$ 的严格下界，记作 $f(n) = \omega(g(n))$ |
例如，对于 $f(n) = 3n^3+2n^2$，取 $n_0 = 1$，当 $n \geqslant n_0 = 1$ 时：
取 $c_1 = 5$，有 $T(n) \leqslant 5n^3$ 成立，即有 $T(n) = \varOmega(n^3)$
取 $c_2 = 3$，有 $T(n) \geqslant 3n^3$ 成立，即有 $T(n) = O(n^3)$
若 $f(n) = o(g(n))$，则有 $\displaystyle \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$
若 $f(n) = \omega(g(n))$，当且仅当 $g(n) \in o(f(n))$
函数阶的性质
| 性质 | 表达式 |
|---|---|
| 传递性 | $f(n) = \varTheta(g(n))$ 且 $g(n) = \varTheta(h(n))$，则有 $f(n) = \varTheta(h(n))$ |
| 自反性 | $f(n) = \varTheta(f(n))$，$f(n) = \Omega(f(n))$，$f(n) = O(f(n))$ |
| 对称性 | 若 $f(n) = \Omega(g(n))$，则有 $g(n) = O(f(n))$ |
| 反对称性 | $f(n) = O(g(n))$，当且仅当 $g(n) \in \Omega(f(n))$ |
并非所有函数都是可比的，例如 $f(n) = n$ 和 $g(n) = n^{1+\sin n}$
多项式时间的算法之间有差距，但一般可接受。
指数量级的算法对于较大的 $n$ 无使用价值。
和的估计与界限
直接求和
$\displaystyle \sum_{k=1}^{n} a_k \leqslant n \max_{1 \leqslant k \leqslant n} a_k$
例如：$\displaystyle \sum_{k=1}^{n} k \leqslant \sum_{k=1}^{n} n \leqslant n^2$
对于所有 $k>0$，都有 $\frac{a_{k+1}}{a_k} \leqslant r < 1$，则 $\displaystyle \sum_{k=1}^{n} a_k \leqslant \sum_{k=1}^{n} a_0 r^k \leqslant \frac{a_0}{1-r}$
求和转换为积分
当 $f(x)$ 单调递增时，有 $\displaystyle \int_{m-1}^{n} f(x) \mathrm{d}x \leqslant \sum_{k=m}^{n} f(x) \leqslant \int_{m}^{n+1} f(x) \mathrm{d}x $
当 $f(x)$ 单调递减时，有 $\displaystyle \int_{m}^{n+1} f(x) \mathrm{d}x \leqslant \sum_{k=m}^{n} f(x) \leqslant \int_{m-1}^{n} f(x) \mathrm{d}x $
例如，在算法分析中经常出现的 $\log n!$ 可作如下分析：
由对数运算性质可知，
$$ \log n! = \sum_{k=1}^{n} \log k $$则有上界：
$$ \sum_{k=1}^{n} \log k \leqslant \int_{1}^{n+1} \log x \mathrm{d}x $$积分求和的上界
同理，可知下界：
$$ \sum_{k=1}^{n} \log k \geqslant \int_{0}^{n} \log x \mathrm{d}x $$积分求和的下界
综合两式可得：$\log n! = \varTheta(n\log n)$，该求和公式在快速排序等算法中有重要作用。
递归方程
逐层展开法
案例：归并排序的递归方程
$$T(n) = \left\{ \begin{matrix} \begin{align*} &\varTheta(1), & n=1 \\\\ &2T\displaystyle \left(\frac{n}{2}\right) + \varTheta(n), & n \geqslant 1 \end{align*} \end{matrix} \right.$$将其展开可得：
$$\begin{align*} T(n) &= n + 3T\left(\left\lfloor \frac{n}{4} \right\rfloor\right) \\\\ &= n + 3\left(\left\lfloor \frac{n}{4} \right\rfloor + 3T\left( \left\lfloor \frac{n}{16} \right\rfloor \right)\right) \\\\ &= n + 3\left\lfloor \frac{n}{4} \right\rfloor + 3^2 \left\lfloor \frac{n}{4^2} \right\rfloor + 3^3 \left\lfloor \frac{n}{4^3} \right\rfloor + \cdots + 3^k T \left(\left\lfloor \frac{n}{4^k} \right\rfloor \right) \end{align*}$$深度 $k = \log_{4}n$，最底层有 $3^k = 3^{\log_{4}n} = n^{\log_{4}3}$ 个，则有
$$T(n) = \sum_{i=0}^{(\log_{4}n) - 1} 3^i \cdot \frac{n}{4^i} + \varTheta(n^{\log_{4}3}) \leqslant 4n + \varTheta(n^{\log_{4}3}) = O(n)$$变量替换法
设递归方程为：
$$T(n) = 2T(\sqrt{n}) + \log n$$令 $m = \log n$，则 $n = 2^m$，$\displaystyle T(2^m) = 2T\left(2^{\frac{m}{2}}\right) + m$
令 $S(m) = T(2^m)$，则 $\displaystyle S\left(\frac{m}{2}\right) = T\left(2^{\frac{m}{2}}\right)$
于是 $\displaystyle S(m) = 2S\left(\frac{m}{2}\right) + m = \varTheta(m \log m)$
回代可得 $T(n) = \varTheta(\log n (\log (\log n)))$
Master定理
求解形如 $\displaystyle T(n) = a \cdot T\left(\frac{n}{b}\right) + f(n)$ 的递归方程（其中 $a \geqslant 1$，$b \geqslant 1$ 是常数，$f(n)$ 是正函数）。
- 若 $f(n) = O(n^{(\log_{b} a)-\varepsilon})$，常数 $\varepsilon > 0$，则有 $T(n) = \varTheta(n^{\log_{b}a})$
- 若 $f(n) = \varTheta(n^{\log_{b} a})$，则有 $T(n) = \varTheta(n^{\log_b a} \log n)$
- 若 $f(n) = \varOmega(n^{(\log_{b} a) + \varepsilon})$，常数 $\varepsilon > 0$，且对所有 $n$，都有 $af(\frac{n}{b}) \leqslant c \cdot f(n)$ （$c<1$ 且为常数），则有 $T(n) = \varTheta(f(n))$
直观理解：用 $f(n)$ 与 $n^{\log_b a}$ 的阶比较
- 若 $n^{\log_b a}$ 的阶更大，即 $f(n)$ 的阶不仅小于 $n^{\log_b a}$，而且还小于 $n^{\log_b a}/n^{\varepsilon}$，则 $T(n) = \varTheta(n^{\log_b a})$
- 若 $f(n) = \varTheta(n^{\log_b a})$，即 $f(n)$ 与 $n^{\log_b a}$ 同阶，则有 $T(n) = \varTheta(n^{\log_b a} \log n) = \varTheta(f(n)\log n)$
- 若 $f(n)$ 的阶更大，即 $f(n)$ 的阶不仅大于 $n^{\log_b a}$，而且还大于 $n^{\log_b a} \cdot n^{\varepsilon}$，则 $T(n) = \varTheta(f(n))$
Master定理证明（点击展开）
对 $\displaystyle f(n) = a T(\frac{n}{b}) + f(n)$ 展开可得
$$ T(n) = \varTheta(n^{\log_b a}) + \sum_{i=0}^{k-1} a^i \cdot f(\frac{n}{b^i}) $$其中 $n = b^k$，$k = \log_b n$，$a^k = a^{\log_b n} = n^{\log_b a}$
令 $\displaystyle g(n) = \sum_{i=0}^{k-1} a^i f\left( \frac{n}{b^i} \right)$， 则有 $T(n) = \varTheta(n^{\log_b a}) + g(n)$
-
若 $f(n) = O(n^{(\log_b a) - \varepsilon})$，则有
$$\begin{align*} g(n) &= O \left(\sum_{i=0}^{k-1} a^i \left(\frac{n}{b^i}\right)^{(\log_b a)-\varepsilon} \right) = O \left( n^{(\log_b a)-\varepsilon} \sum_{i=0}^{k-1} \left(\frac{ab^{\varepsilon}}{b^{\log_b a}}\right)^i \right) \\ &= O \left( n^{(\log_b a)-\varepsilon} \frac{n^{\varepsilon} - 1}{b^{\varepsilon} - 1} \right) = O(n^{\log_b a}) \end{align*}$$故 $T(n) = \varTheta(n^{\log_b a}) + g(n) = \varTheta(n^{\log_b a})$
-
若 $f(n) = \varTheta(n^{\log_b a})$，则有
$$\begin{align*} g(n) &= \varTheta \left( \sum_{i=0}^{k-1} a^i \frac{n}{b^i}^{\log_b a} \right) = \varTheta \left( n^{\log_b a} \sum_{i=0}^{k-1} 1 \right) \\ &= \varTheta(n^{\log_b a} k) = \varTheta(n^{\log_b a} \log_b n) = \varTheta(n^{\log_b a} \log n) \end{align*}$$故 $T(n) = \varTheta(n^{\log_b a}) + g(n) = \varTheta(n^{\log_b a} \log n)$
-
若 $f(n) = \varOmega(n^{(\log_b a) + \varepsilon})$，且对所有充分大的 $n$ 有
$$\begin{align*} a f(\frac{n}{b}) &\leqslant c f(n) \\ a f(\frac{n}{b^2}) &\leqslant c f(\frac{n}{b}) \\ &\cdots \\ a f(\frac{n}{b^i}) &\leqslant c f(\frac{n}{b^{i-1}}) \end{align*}$$两边分别相乘得 $\displaystyle a^i f(\frac{n}{b^i}) \leqslant c^i f(n)$，则有
$$g(n) = \sum_{i=0}^{k-1} a^i f(\frac{n}{b^i}) \leqslant \sum_{i=0}^{k-1} c^i f(n) = f(n) \sum_{i=0}^{k-1} c^i \leqslant f(n) \cdot \frac{1}{1-c} = \varTheta(f(n))$$故 $T(n) = \varTheta(n^{\log_b a}) + g(n) = \varTheta(f(n))$
推广形式：若 $f(n) = \varTheta(n^{\log_b a} \log^{k} n)$，其中 $k \geqslant 0$，则有 $T(n) = \varTheta(n^{\log_b a} \log^{k+1} n)$