计算机科学并不只是关于计算机，就像天文学并不只关于望远镜一样。

― Edsger Dijkstra

参考资料：点击此处

特别感谢由 NoviaMiller 提供的AI总结！

算法的基本概念

算法是对特定问题求解的一种描述，是指令的有限序列。

算法的特点

• 有穷性：在有限步骤内结束，有限时间内完成。
• 确定性：每条指令都是明确的、无二义的。
• 可行性：每条指令都能够被执行。
• 输入：有0个或多个输入变量。
• 输出：有1个或多个输出变量、

算法的正确性

📝 备注

调试程序 $\ne$ 程序正确性的证明。程序调试只能证明程序是否有错，不能证明程序正确（无错误）。

算法的优劣

单纯使用程序执行时间衡量算法的优劣缺乏客观性，因此需要使用独立于具体计算机的客观衡量标准。

• 问题的规模：一个或多个整数，作为输入数据量的测度。
• 复杂度：
  • 时间复杂度：基本运算（原子操作）的执行次数。
  • 空间复杂度：算法所需存储空间的大小。
• 基本运算：解决给定问题时占支配地位的运算。讨论一个算法的优劣通常只考虑基本运算。

算法分析的数学基础

复杂性函数的阶

渐进复杂性

渐进复杂性表达了当输入规模 $n$ 趋近于极限（相当大）时的复杂性 $T(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) = \Omega(n^3)$
• 取 $c_2 = 3$，有 $T(n) \geqslant 3n^3$ 成立，即有 $T(n) = \mathrm{O}(n^3)$

综上，$T(n) = \Omega(n^3)$

定理：对于任意的 $f(n)$ 和 $g(n)$，$f(n) = \Theta(g(n))$ 当且仅当 $f(n) = \mathrm{O}(g(n))$ 且 $f(n) = \Omega(g(n))$。

证明：先证明必要性：若 $f(n) = \Theta(g(n))$，则存在 $c_1, c_2 > 0$，$n_0 > 0$，使得当 $n \geqslant n_0$ 时都有 $c_1 g(n) \leqslant f(n) \leqslant c_2 g(n)$，则 $f(n) = \mathrm{O}(g(n))$ 且 $f(n) = \Omega(g(n))$

再证明充分性：若 $f(n) = \mathrm{O}(g(n))$ 且 $f(n) = \Omega(g(n))$，

• 由 $f(n) = \mathrm{O}(g(n))$ 可知存在 $c_1, n_1 > 0$，使得当 $n \geqslant n_1$ 时有 $f(n) \leqslant c_1 g(n)$；
• 由 $f(n) = \Omega(g(n))$ 可知存在 $c_2, n_2 > 0$，使得当 $n \geqslant n_2$ 时有 $f(n) \geqslant c_2 g(n)$。

令 $n_0 = \max \{n_1, n_2\}$，则当 $n>n_0$时，有 $c_2 g(n) \leqslant f(n) \leqslant c_1 f(n)$，即 $f(n) = \Theta(g(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) = 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) = n$ 与 $g(n) = n^{1+\sin n}$ 之间就找不到符合要求的 $n_0$ 和 $c$。

定义了函数的阶之后，就可以量化程序运行的时间了。例如，对于一台每秒可执行某基本运算 $10^9$ 次的机器，当输入规模为 $60$ 时：

由此可得出两个结论：

1. 多项式时间的算法之间有差距，但一般可接受。
2. 指数量级的算法对于较大的 $n$ 无使用价值。

和的估计与界限

直接求和

特别地：$\displaystyle \sum_{k=1}^{n} k \leqslant \sum_{k=1}^{n} n \leqslant n^2$

对于所有 $k>0$，若都有 $\displaystyle \frac{a_{k+1}}{a_k} \leqslant r < 1$，则

求和转换为积分

当 $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} \log x \mathrm{d}x $$

同理，可知下界：

$$ \sum_{k=1}^{n} \log k \geqslant \int_{2}^{n+1} \log (x-1) \mathrm{d}x \xlongequal{t = x-1} \int_{1}^{n} \log t \mathrm{d}t = \int_{1}^{n} \log x \mathrm{d}x$$

综合两式可得：$\log n! = \Theta(n\log n)$，该求和公式在 快速排序 等算法中有重要作用。

递归方程

递归方程是用递归形式描述算法时间复杂度的有效工具，通过求解递归方程可以快速得知算法的时间复杂度信息。

例如：归并排序的递归方程

逐层展开法

对于递归方程

将其展开可得：

深度 $k = \log_{4}n$，最底层有 $3^k = 3^{\log_{4}n} = n^{\log_{4}3}$ 个，则有

变量替换法

设递归方程为：

令 $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)$

于是

回代可得 $T(n) = \Theta(\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)$ 是正函数）：

1. 若 $f(n) = \mathrm{O} (n^{(\log_{b} a)-\varepsilon})$，常数 $\varepsilon > 0$，则有 $T(n) = \Theta(n^{\log_{b}a})$
2. 若 $f(n) = \Theta(n^{\log_{b} a})$，则有 $T(n) = \Theta(n^{\log_b a} \log n)$
3. 若 $f(n) = \Omega(n^{(\log_{b} a) + \varepsilon})$，常数 $\varepsilon > 0$，且对所有 $n$，都有 $\displaystyle af\left(\frac{n}{b}\right) \leqslant c \cdot f(n)$ （$c>1$ 且为常数），则有 $T(n) = \Theta(f(n))$

直观理解：用 $f(n)$ 与 $n^{\log_b a}$ 的阶比较

1. 若 $n^{\log_b a}$ 的阶更大，即 $f(n)$ 的阶不仅小于 $n^{\log_b a}$，而且还小于 $n^{\log_b a}/n^{\varepsilon}$，则 $T(n) = \Theta(n^{\log_b a})$
2. 若 $f(n) = \Theta(n^{\log_b a})$，即 $f(n)$ 与 $n^{\log_b a}$ 同阶，则有 $T(n) = \Theta(n^{\log_b a} \log n) = \Theta(f(n)\log n)$
3. 若 $f(n)$ 的阶更大，即 $f(n)$ 的阶不仅大于 $n^{\log_b a}$，而且还大于 $n^{\log_b a} \cdot n^{\varepsilon}$，则 $T(n) = \Theta(f(n))$

推广形式：若 $f(n) = \Theta(n^{\log_b a} \log^{k} n)$，其中 $k \geqslant 0$，则有

$$T(n) = \Theta(n^{\log_b a} \log^{k+1} n)$$

算法实例

这里仅给出一些算法的案例。

NP问题分析

本部分我们不再研究具体的算法，而是抽象地研究算法解决的这些计算问题。即对于给定的问题，我们关注于：

1. 是否可以计算？
2. 如果可以计算，如何判断是计算易解的还是难解的？
3. 如果是难解的，如何判断与哪些已知难解问题是等价的？
4. 如果不可以计算，如何证明？

抽象问题 $Q$ 定义为问题实例空间 $I$ 和问题解空间 $S$ 上的二元关系：$Q = (I, S)$。

决策问题与优化问题

决策问题（Decision problem）：只要求回答“Yes”或“No”的问题，它的解空间只含有两个元素 $\{\text{yes}, \text{no}\}$，也称为判定问题。如判断图中两点之间是否存在长度不超过 $k$ 的路径。

优化问题（Optimization problem）：要求在所有的可行解里找出使得目标函数最大或最小的解。如找出图中两点之间的最短路径。

任何优化问题，都可以转化为相应的决策问题。

1. 定义决策问题的阈值：转化为一个“是否存在满足该约束的解”的问题。
2. 利用二分法算法逼近优化解：通过决策问题解决原优化问题。

例如，对于旅行商问题（TSP）：

1. 优化问题描述：找出图中长度最小的汉密尔顿回路。
2. 决策问题描述：是否存在一条长度 $\leqslant k$ 的汉密尔顿回路。
3. 二分搜索：首先确定目标函数的下界 $L = 0$ 和上界 $U = \Sigma e_i$ ，然后在区间 $[L,U]$ 内进行二分搜索，取中点 $\displaystyle k = \frac{L+U}{2}$，调用决策问题算法：若答案为“yes”，说明最优值 $\leqslant k$ ，更新 $U = k$；若答案为“No”，说明最优值 $> k$，更新 $L=k+1$

优化问题转化为决策问题的复杂度分析：

1. 设二分搜索算法的时间复杂度为 $T_b$，解决对应决策问题的算法的时间复杂度为 $T_d$，则通过二分搜索结合决策问题的解法求解优化问题时，总的时间复杂度为 $$T_o = \mathrm{O} (T_b \cdot T_d)$$
2. 二分搜索的时间复杂度 $T_b$ 取决于参数 $k$ 的取值范围（长度）。若 $k$ 的取值上限（长度）是输入实例规模 $n$ 的多项式函数，则 $T_b$ 是 $\mathrm{O} (\log 𝑛)$，即具有多项式对数时间复杂度。此时，整体时间复杂度 $T_o$ 与 $T_d$ 属于同一复杂度量级。
3. 因而求解决策问题可以近似求解优化问题，这表明优化问题至少与相应的决策问题一样难。

问题的难易

易解问题（Tractable problems）: 如果问题 $Q$ 存在一个多项式界的求解算法，则称问题 $Q$ 为易解（计算）问题（computationally tractable）。

易解问题算法的上界是多项式界，例如 $\log n$，$n\log n$，$n^2$ 等。这类问题复杂性的上界约束只适用于合理的输入实例尺寸。

当前不是易解的问题，将来可能会变为易解问题。

难解问题（Intractable problems）：不存在多项式界求解算法的问题，即求解该问题算法的复杂性至少是指数级的。

不可解问题（unsolvable problem）：不能被确定型图灵机求解的计算问题，即不存在任何算法能够求解的计算问题，通常也称为不可判定问题（Undecidable）。例如停机问题。

停机问题可以描述为：是否存在一个程序 $P$，对于任意输入的程序 $w$，能够判断 $w$ 会在有限时间内结束或者死循环。

假设停机问题有解，则存在算法halt(P,I)可以判断对于输入I时程序P是否停机，即：

$$\text{halt}(P,I) = \left\{ \begin{matrix} \begin{align*} & \text{Yes} & \text{if输入I, P停机} \\ & \text{No} & \text{if输入I, P进入死循环} \end{align*} \end{matrix} \right.$$

构造下面的程序 $Z(P)$，它实现了当程序 $P$ 读入其本身 $P$ 时，如果halt算法判定其停机，则 $Z$ 进入死循环，否则 $Z$ 停机：

1 2 3 4 5

Z(P) { a: if halt(P,P) then goto a; else halt; }

1. Case 1：程序 $Z$ 关于输入 $Z$ 停机：halt判定其停机，而程序 $Z$ 判定其进入死循环。
2. Case 2：程序 $Z$ 关于输入 $Z$ 进入死循环：halt判定其进入死循环，而程序 $Z$ 判定其停机

因而halt(P,I)不存在，停机问题是不可解（计算）的！

合理的输入尺寸

满足以下两个条件的输入为合理的输入尺寸：

• 期望的输出与输入密切相关。
• 输入可以被确定编码。

📝 备注

• 在《算法》教材里，查找含有“NP 问题” 的段落：合理；
• 在整个互联网里，查找含有“NP 问题”的网页：不合理；
• 在人类基因组里，查找某个基因：合理；
• 在所有物种里，查找某个基因：不合理。

难解问题的时效性

难解问题不一定永远不能转变为易解问题。

案例：素数检验问题（给定任意正整数 $n$，检验 $n$ 是否存在大于 $1$ 的整数因子）

直到 2004 年，AKS（M. Agrawal, N. Kayal, and N. Saxena）在美国数学年报上提出了复杂性是 $n$ 位数的多项式函数的算法。

问题难的原因

输入实例的长度

在算法复杂性理论中，输入实例的长度是度量一个计算问题规模的基本单位，是分析算法时间复杂度和空间复杂度的基础。

输入实例长度通常是指描述该输入所需的比特数，即用某种固定编码方式将输入表示为二进制字符串时的长度。

设有一个计算问题，其输入是一个字符串 $x \in \Sigma$，其中 $\Sigma$ 是某个有限字符集（如 $\{0, 1\}$）。那么输入实例 $x$ 的长度可以形式化地表示为 $|x|$，即表示这个字符串所需字符的个数。

📝 备注

注意：算法复杂性研究的是输入实例长度与复杂性之间的关系，而非输入特征。当我们用近似符号表示算法复杂性时，需要判断输入特征与输入长度是否满足多项式关系：

• 是：可以使用近似符号表示输入特征与复杂性的关系。
• 否：不能直接使用，需要推导输入长度与复杂性的关系。

例如对于0/1背包问题，输入实例 $n$，$c$，$w=(w_1, w_2, \cdots, w_n)$，$p=(p_1, p_2, \cdots, p_n)$。则输入实例长度可表示为

所以 $T = \Theta(nc) = \Theta(n2^m)$ 是伪多项式界。

非确定性算法

非确定性算法指的是算法多次运行同样的输入实例时，可能表现出不同的行为（例如某个时刻有多个动作可供选择），从而导致不同的运行结果。

导致不确定的原因:

• 概率算法：动作（指令）的执行依赖于随机数的产生。
• 并发算法：动作（指令）的执行结果依赖于竞态条件。

问题难的等价性

P类问题

$\text{P}$ 类问题：能够被确定性图灵机在多项式时间内求解的决策问题集合。

$\text{P}$ 类问题的性质：

• 高效性：多项式时间复杂性意味着算法的运行时间增长率是温和的、可控的，不会随输入规模 $n$ 的增加而呈指数级爆炸。
• 多项式时间可解：任何在图灵机上多项式时间可解的问题，在任何合理的计算模型（包括现代计算机）上，也是多项式时间可解的。
• 封闭性： $\text{P}$ 类对多项式时间的加法、乘法及复合运算是封闭的。这意味着多个 $\text{P}$ 类算法的组合运算结果仍属于 $\text{P}$ 类。

NP类问题

当且仅当存在一个验证算法 $V$（Verifier）和一个多项式 $p$，满足：

• 多项式时间验证：对于任意输入实例 $w$ 和证书 $c$，验证算法 $V$ 的运行时间是输入规模 $|w|$ 的多项式函数，即 $$T(V(w,c)) = \mathrm{O}(p(|w| + |c|))$$
• 证书存在性：对于任意实例 $w$
  • 如果 $w$ 是 $Q$ 的一个 $\text{YES}$ 实例（即 $w \in Q$），则存在一个证书 $c$ 使得验证通过，即 $$V(w, c) = \text{YES}$$
  • 所有满足条件的证书 $c$ 的长度 $|c|$ 具有关于输入大小的多项式界，即 $$|c| = \mathrm{O}(p(|w|))$$

NPC类问题

当且仅当存在一个多项式界的确定性算法 $T$ 满足：

• 对于 $X$ 的每个输入实例 $x$，$T$ 生成一个实例 $T(x)$；
• $x$ 是 $X$ 的一个合法输入实例且对应 $\text{YES}$ 答案当且仅当 $T(x)$ 是 $Y$ 的一个合法输入实例且对应 $\text{YES}$ 答案。

此时称问题 $X$ 可以多项式地规约到问题 $Y$，记做 $X \leqslant_P Y$。

$X \leqslant_P Y$ 意味着 $X$ 至多与 $Y$ 一样难。

如果 $X \leqslant_P Y$ 且 $Y$ 属于 $\text{P}$ 类问题，那么 $X$ 也属于 $\text{P}$ 类问题。

如果所有的 $\text{NP}$ 类问题都可以多项式地规约到问题 $Q$，那么称 $Q$ 为 $\text{NP-hard}$ 问题（$\text{NPH}$）。

$\text{NP-hard}$ 至少和所有 $\text{NP}$ 问题一样难，但它的解可能无法在多项式时间内被验证。

常见的 $\text{NP-hard}$ 问题：

• 3-SAT（布尔可满足性问题）：最万能的起点。
• 旅行商问题（TSP）：常用于路径、网络、图论类问题。
• 背包问题：常用于资源分配、调度类问题。
• 顶点覆盖/团问题：常用于社交网络、图匹配类问题。
• 集合覆盖：常用于选点、选址、广告投放类问题。

如果问题 $Q$ 是 $\text{NP-hard}$ 问题并且也属于 $\text{NP}$ 类问题，那么称 $Q$ 为 NP Complete（$\text{NPC}$）问题。

$\text{NPC}$ 是 $\text{NP}$ 和 $\text{NP-hard}$ 的交集，即 $\text{NPC} = \text{NP} \cap \text{NP-hard}$。

📝 备注

问题属于 $\text{NP-hard}$ 但不属于 $\text{NP}$ 的核心特征就是：问题极难求解，且即使给你一个答案，你也几乎无法在多项式时间内验证它是否正确。

通常，不可解问题（如停机问题）、无法“判定”的最优化问题、需要“找最优解”的搜索问题、非“多项式界限”的验证问题等问题即属于 $\text{NP-hard}$ 但不是 $\text{NP}$ 问题。

$\text{NPC}$ 问题的性质：

• 封闭性：所有的 $\text{NPC}$ 问题关于多项式规约是封闭的；
• 自反性：任何问题 $Q$ 可规约到自身；
• 传递性：如果 $A$ 规约到 $B$，$B$ 规约到 $C$，则 $A$ 规约到 $C$。

如果能够找到一个 $\text{NPC}$ 问题的多项式算法，那么 $\text{P} = \text{NP}$。

$\text{P} = \text{NP}$ 问题位于七个“千僖年数学难题”之首，迄今无解。