--- title: 算法设计与分析复习笔记 author: 萑澈 pubDatetime: 2026-01-14T00:00:00Z featured: false draft: false printable: true tags: - 算法设计 - 数据结构 - cs408 description: 算法设计与分析复习笔记，涵盖 RSA 加密算法、扩展欧几里得求逆元、反复平方算法、0-1 背包问题、动态规划与贪心算法、Levenshtein 编辑距离、矩阵链乘法、快速排序、归并排序、堆排序、Karatsuba 大整数乘法、主定理、渐近时间复杂度（大 O/Θ/Ω）、NP 完全问题归约树、Knuth 算法定义等核心知识点 --- # 算法设计与分析复习笔记 --- # 第一部分：算法基础与 RSA 加密 ![PixPin_2026-01-16_00-24-50.png](https://gastigado.cnies.org/d/graduate/20260116002512723.webp) ## RSA 加密算法 ### 1. 加密过程 | **步骤** | **说明** | **描述** | | ------ | --------------------------------- | --------------------------------- | | **1** | 选择一对 **不相等** 且 **足够大** 的质数 | $p, q$ | | **2** | 计算 $p, q$ 的乘积 | $n = p \times q$ | | **3** | 计算 $n$ 的欧拉函数 | $\varphi(n) = (p-1) \times (q-1)$ | | **4** | 选一个与 $\varphi(n)$ 互质的整数 $e$ | $1 < e < \varphi(n)$ | | **5** | 计算出 $e$ 对于 $\varphi(n)$ 的模反元素 $d$ | $de \bmod \varphi(n) = 1$ | | **6** | 公钥 | $KU = (e, n)$ | | **7** | 私钥 | $KR = (d, n)$ | - **明文** $M$ $\quad \rightarrow \quad$ **加密** $M^e \bmod n = C$ - **密文** $C$ $\quad \rightarrow \quad$ **解密** $C^d \bmod n = M$ #### 计算欧拉函数 - **欧拉函数**是小于 n 的正整数中与 n 互质的数的数目。 - **互质**是公约数只有 1 的两个整数，叫做互质整数。 - **质数**是指在大于 1 的自然数中，除了 1 和它本身以外不再有其他因数的自然数。$\varphi(n)=n-1$ - 如果 $n$ 可以分解成 2 个 **互质** 的整数之积，那么 $n$ 的欧拉函数等于这两个因子的欧拉函数之积。 - 即若 $n = p \times q$，且 $p, q$ 互质，则 $\varphi(n) = \varphi(p \times q) = \varphi(p) \times \varphi(q) = (p-1) \times (q-1)$。 #### 计算模反元素$d$ - 如果两个正整数 $e$ 和 $\varphi(n)$ 互质，那么一定可以找到一个整数 $d$，使得 $ed-1$ 被 $\varphi(n)$ 整除，或者说 $ed$ 除以 $\varphi(n)$ 所得余数为 1。 - 此时，$d$ 就叫做 $e$ 的 **模反元素**。 根据定义，模反元素可以用以下三种等价的数学形式表示： 1. 整除形式： $$ed - 1 = k\varphi(n)$$ 2. 取模运算形式： $$ed \bmod \varphi(n) = 1$$ 3. 同余式形式： $$ed \equiv 1 \pmod{\varphi(n)}$$ 3 和 11，$3\times4-1=11$，那么 $d=4$，那么 $4±k · 11$ 都可以是 d，也就是 $d+k\varphi(n)$ 都是 e 的模反元素。d 不唯一，一般取最小的那个便于计算。 #### 证明 - **明文** $M$ $\quad \rightarrow \quad$ **加密** $M^e \bmod n = C$ - **密文** $C$ $\quad \rightarrow \quad$ **解密** $C^d \bmod n = M$ 不考，不学了 ### 2. 例题 #### 第一步：密钥生成 (Key Generation) 1. **确定参数：** - 已知：$p = 5$, $q = 11$, $e = 3$。 2. 计算公共模数 $n$： $$n = p \times q = 5 \times 11 = 55$$ 3. 计算欧拉函数 $\phi(n)$： $$\phi(n) = (p-1)(q-1) = (5-1)(11-1) = 4 \times 10 = 40$$ 4. 计算私钥 $d$： $d$ 是 $e$ 关于 $\phi(n)$ 的模反元素，需满足：$(d \times e) \equiv 1 \pmod{\phi(n)}$。 即：$(d \times 3) \equiv 1 \pmod{40}$。 - 经计算：$3 \times 27 = 81$。 - $81 \div 40 = 2$ 余 $1$。 - 因此，$d = 27$。 **结果：** - **公钥 (Public Key):** $(n=55, e=3)$ - **私钥 (Private Key):** $(n=55, d=27)$ --- #### 第二步：加密过程 (Encryption) 已知明文 $m = 14$，加密公式为：$c = m^e \pmod n$。 1. 代入数据：$c = 14^3 \pmod{55}$ 2. 计算：$14^3 = 2744$ 3. 取模：$2744 \div 55 = 49$ 余 $49$ - ($55 \times 49 = 2695$) - $2744 - 2695 = 49$ **加密结果：** 密文 $c = 49$。 --- #### 第三步：解密过程 (Decryption) 使用私钥对密文 $c = 49$ 进行解密，公式为：$m = c^d \pmod n$。 1. 代入数据：$m = 49^{27} \pmod{55}$ 2. **简化计算 (使用快速幂取模法)：** - $49 \equiv -6 \pmod{55}$ - $49^2 \equiv (-6)^2 = 36 \equiv -19 \pmod{55}$ - $49^3 \equiv 36 \times (-6) = -216$。$-216 \div 55$ 的余数为 $4$（因为 $55 \times (-4) = -220$）。 - 通过幂运算最后可得出：$49^{27} \equiv 14 \pmod{55}$。 **解密结果：** 明文 $m = 14$（与原始明文一致，验证成功）。 --- #### 总结 - **中间参数：** $n = 55, \phi(n) = 40, d = 27$ - **加密结果：** 密文为 **49** - **解密结果：** 明文为 **14** #### 注意余数的缩放 你对被除数和除数同时约分（同时除以 5）时，**余数也随之缩小了 5 倍**。 在模运算中有一个重要的性质： > 如果 $a \div b = q \dots r$ （即 $a = bq + r$） > 那么当我们将 $a$ 和 $b$ 同时除以 $k$ 时： > $(a/k) = (b/k)q + (r/k)$ 在你这里： - 原始算式：$100000 = 35 \times 2857 + \mathbf{R}$ - 约分后的算式：$20000 = 7 \times 2857 + \mathbf{1}$ 要还原回原始算式的余数 $R$，你需要把约分掉的 5 乘回去： $$R = 1 \times 5 = 5$$ - **你的计算结果：** 余数 1 是 $20000 \div 7$ 的结果。 - **实际要求的解：** 是 $100000 \div 35$ 的余数。 - **修正方法：** 约分计算完余数后，必须**乘以约掉的那个公约数**。 所以：$1 \times 5 = 5$，这也就是为什么我在上一个回答中算出的明文结果是 **5**。 ##### 💡 小贴士：如何避免这种错误？ 在处理 RSA 这种大数取模时，建议使用**“取模性质”**分步计算，而不是先把大数算出来再除，这样不容易出错： - $10^2 = 100 \equiv 30 \pmod{35}$ - $10^4 = 30 \times 30 = 900$ - $900 \div 35 = 25 \dots 25$ （即 $10^4 \equiv 25 \pmod{35}$） - $10^5 = 10^4 \times 10 = 250$ - $250 \div 35 = 7 \dots \mathbf{5}$ 这种方法数字更小，不容易在约分上栽跟头。 **（$A \times B$）对 $N$ 取模，等于（$A$ 对 $N$ 取模的结果 $\times$ $B$ 对 $N$ 取模的结果）再对 $N$ 取模。** 下面我把每一步拆解得更详细一些： 1. $10^2 = 100 \equiv 30 \pmod{35}$ - **计算：** $10 \times 10 = 100$。 - **取模：** $100 \div 35 = 2 \dots$ 余 $30$。 - **意义：** 在接下来的计算中，凡是遇到 $10^2$ 的地方，我们都可以用它的余数 **$30$** 来代替。 2. $10^4 = 30 \times 30 = 900$ - **计算：** $10^4$ 其实就是 $10^2 \times 10^2$。 - **替换：** 根据取模原理，我们直接用刚才算出的余数代替：$30 \times 30 = 900$。 - **取模：** $900 \div 35 = 25 \dots$ 余 **$25$**。 - _验证：$35 \times 25 = 875$，$900 - 875 = 25$。_ - **意义：** 现在我们知道了 $10^4 \equiv 25 \pmod{35}$。 3. $10^5 = 10^4 \times 10 = 250$ - **计算：** 题目要求的是 $10^5$，它等于 $10^4 \times 10^1$。 - **替换：** 我们用刚才算出的 $10^4$ 的余数 **$25$** 来代替它：$25 \times 10 = 250$。 - **取模：** $250 \div 35 = 7 \dots$ 余 **$5$**。 - _验证：$35 \times 7 = 245$，$250 - 245 = 5$。_ 通过这种方法，你处理的最大数字只是 $900$ 和 $250$，而不是 $100,000$。 如果你觉得 $30$ 还是太大，甚至可以利用 **“负余数”**： - $100 \div 35$ 也可以看作是：差 $5$ 就到 $105$（$35 \times 3$）了。 - 所以 $100 \equiv -5 \pmod{35}$。 - 那么 $10^4 = (10^2)^2 \equiv (-5)^2 = \mathbf{25} \pmod{35}$。 - 最后 $10^5 = 25 \times 10 = 250 \equiv \mathbf{5} \pmod{35}$。 这样计算量会进一步减小。这种分段处理余数的方法在 RSA 算法（尤其是处理大位数密钥时）是必须使用的，被称为 **“模幂运算”**。 ### 3. 扩展欧几里得求乘法逆元 用推广的 Euclid 算法求 67mod119 的逆元。 我们要找一个整数 (x)，使得 $$ 67x \equiv 1 \pmod{119} $$ 等价于存在整数 (k)，满足 $$ 67x + 119k = 1 $$ 👉 **这就是一个典型的线性丢番图方程** $$ 67x + 119y = 1 $$ 只要 $\gcd(67,119)=1$，这个方程就有整数解，而 **推广的 Euclid 算法**正是用来： * 判断是否互质 * 并且**构造出**这样的 (x,y) #### 第一步：辗转相除法（求最大公约数） 我们先用较大的数除以较小的数，直到余数为 0： 1. $119 = 1 \times 67 + 52$ 2. $67 = 1 \times 52 + 15$ 3. $52 = 3 \times 15 + 7$ 4. $15 = 2 \times 7 + 1$ （出现 1，说明 $67$ 和 $119$ 互质，逆元存在） 5. $7 = 7 \times 1 + 0$ * 最后一个非零余数是 **1** * 所以 $$ \gcd(67,119)=1 $$ * ✅ **逆元存在** > ⚠️ 很重要的一点： > **不是所有模数都有逆元，只有当 $\gcd(a,m)=1$ 时，(a) 才在模 (m) 下可逆** --- #### 第二步：回代法（求逆元） > **把“1”一步一步写成“67 和 119 的线性组合”** 也就是最终要得到： $$ 1 = (\text{某个数})\cdot 67 + (\text{某个数})\cdot 119 $$ 其中 **67 前面的系数**，就是我们要的逆元（模 119 意义下）。 现在我们从余数为 **1** 的等式开始，反向代入上述等式： 1. 由第 (4) 式得：**$1 = 15 - 2 \times 7$** 2. 代入第 (3) 式中的 $7 = 52 - 3 \times 15$： $1 = 15 - 2 \times (52 - 3 \times 15)$ $1 = 15 - 2 \times 52 + 6 \times 15$ $1 = 7 \times 15 - 2 \times 52$ 3. 代入第 (2) 式中的 $15 = 67 - 1 \times 52$： $1 = 7 \times (67 - 52) - 2 \times 52$ $1 = 7 \times 67 - 7 \times 52 - 2 \times 52$ $1 = 7 \times 67 - 9 \times 52$ 4. 代入第 (1) 式中的 $52 = 119 - 1 \times 67$： $1 = 7 \times 67 - 9 \times (119 - 67)$ $1 = 7 \times 67 - 9 \times 119 + 9 \times 67$ $1 = 16 \times 67 - 9 \times 119$ --- #### 第三步：得出结果 根据最后一个等式 $1 = 16 \times 67 - 9 \times 119$，在模 $119$ 的环境下： - $-9 \times 119$ 会变成 $0$。 - 等式变为 $1 \equiv 16 \times 67 \pmod{119}$。 结论： $67 \pmod{119}$ 的逆元是 16。 #### 方法二：矩阵表格法（求逆元） **矩阵表格法 = 把回代过程提前，用递推自动完成**。这种方法通过建立一个表格，省去了回代的麻烦。我们还是求 $67 \pmod{119}$ 的逆元。 回代法里你做的是： - 一层一层代 - 每次更新「当前余数 = 前两个余数的线性组合」 表格法只是把： $$ 1 = a_i\cdot 119 + b_i\cdot 67 $$ 中的 **$b_i$**（67 的系数）提前算出来。 **口诀：** 先排好商 $q$，从 $0, 1$ 开始，计算公式为 $x_i = x_{i-2} - q_{i-1} \times x_{i-1}$。 1. **先做辗转相除得到商 $q$：** - $119 \div 67 = \mathbf{1}$ 余 $52$ - $67 \div 52 = \mathbf{1}$ 余 $15$ - $52 \div 15 = \mathbf{3}$ 余 $7$ - $15 \div 7 = \mathbf{2}$ 余 $1$​ **真正被用到的不是余数，而是“商”**。表格法 **只吃商，不管余数** $$ \boxed{q = [1,\;1,\;3,\;2]} $$ 2. **填表：** | **步骤** | **商 q** | **序列 x (逆元所在列)** | **计算过程** | | ------ | ------- | ---------------- | ------------------------ | | -2 | | **0** | (初始值) | | -1 | | **1** | (初始值) | | 1 | 1 | **-1** | $0 - (1 \times 1) = -1$ | | 2 | 1 | **2** | $1 - (1 \times -1) = 2$ | | 3 | 3 | **-7** | $-1 - (3 \times 2) = -7$ | | 4 | 2 | **16** | $2 - (2 \times -7) = 16$ | **结果：** 最后一行的 **16** 就是逆元。 ### 4. 反复平方算法 **反复平方算法的目标：** > 用 **$O (\log n)$** 次运算 > 代替 **$O (n)$** 次连乘 **把指数写成二进制，把幂次拆成若干个平方** 也就是： $$ a^n = a^{2^k_1}\cdot a^{2^k_2}\cdots $$ 而每个 $a^{2^k}$ 都可以通过“平方前一个”得到。 1️⃣ 指数拆分 $$ n = \sum b_i 2^i \quad (b_i\in{0,1}) $$ 2️⃣ 模运算与乘法兼容 $$ (ab)\bmod m = ((a\bmod m)(b\bmod m))\bmod m $$ 👉 所以我们可以： - 每一步都 **先取模** - 数字永远不会变大 #### 算法步骤 ##### Step 1：指数二进制化 把 n 写成二进制。 ##### Step 2：反复平方（预处理） 依次计算： $$ \begin{aligned} a^{2^0} &\equiv a \pmod m \\ a^{2^1} &\equiv a^2 \pmod m \\ a^{2^2} &\equiv (a^2)^2 \pmod m \\ a^{2^3} &\equiv (a^2)^4 \pmod m \\ &\vdots \end{aligned} $$ ##### Step 3：按二进制位相乘 只乘 **二进制中为 1 的位** 对应的幂。 #### 示例 计算 $14^3 \pmod{55}$ 虽然指数小，但**流程完全一样**。 ------ ##### Step 1：指数二进制化 $$ 3 = (11)_2 = 2^1 + 2^0 $$ ------ ##### Step 2：反复平方（每一步都取模） 第 1 项： $$ 14^{2^0} \equiv 14 \pmod{55} $$ 第 2 项： $$ 14^{2^1} = 14^2 = 196 $$ $$ 196 \bmod 55 = 196 - 3\times55 = 31 $$ 所以： $$ 14^2 \equiv 31 \pmod{55} $$ ------ ##### Step 3：选中二进制为 1 的幂相乘 因为： $$ 14^3 = 14^{2^1}\cdot14^{2^0} $$ 所以： $$ 14^3 \equiv 31 \times 14 \pmod{55} $$ 计算： $$ 31\times14 = 434 $$ $$ 434 \bmod 55 = 434 - 7\times55 = 49 $$ ------ ##### 🎯 最终答案 $$ \boxed{14^3 \equiv 49 \pmod{55}} $$ #### 表格解法 ##### 计算 $$ 10^{27} \pmod{55} $$ ------ ##### Step 1：指数二进制化 $$ 27 = (11011)_2 = 16+8+2+1 $$ ------ ##### Step 2：表格法 | i | $e_i$ | $10^{2^i} \bmod 55$ | 累积结果 | | --- | ----- | ------------------- | -------------------- | | 0 | 1 | $10$ | $1\times10=10$ | | 1 | 1 | $10^2=100\equiv45$ | $10\times45\equiv10$ | | 2 | 0 | $45^2=2025\equiv45$ | 不变 | | 3 | 1 | $45^2\equiv45$ | $10\times45\equiv10$ | | 4 | 1 | $45^2\equiv45$ | $10\times45\equiv10$ | ------ ##### 最终结果 $$ \boxed{10^{27} \equiv 10 \pmod{55}} $$ ### 5. 时间复杂度 RSA 加密与解密的主要计算为模指数运算，采用快速幂算法，其时间复杂度为 $O(\log n)$ 次模乘运算。 ### 6. RSA 的计算可行性和不可攻破性 #### 可行性 已知 p,q，就能：轻松算φ(n)，用扩展 Euclid 算 d 模指数运算可以用快速幂 **RSA 的密钥生成和加解密过程均可通过多项式时间算法完成，尤其是模指数运算可采用反复平方算法，因此在计算上是可行的。** #### 不可攻破性 已知 n，不知道 p,q，无法得到μ(n)，无法求 d **在现有计算能力和已知算法条件下，大整数因子分解问题是计算上不可行的，因此 RSA 具有不可攻破性。** ## 0-1 背包问题 ![PixPin_2026-01-16_11-42-45.png](https://gastigado.cnies.org/d/graduate/20260116114248093.webp) 1️⃣ 子问题定义（非常关键） > 令 `dp[i][j]` 表示： > **从前 i 个物品中选择，背包容量为 j 时可获得的最大价值。** 2️⃣ 边界条件 - `dp[0][j] = 0`（没有物品） - `dp[i][0] = 0`（容量为 0） ### 例题 ![image.png](https://gastigado.cnies.org/d/graduate/20260113162510040.webp) > **dp\[i\]\[j\] = > 在「只考虑前 i 个物品」的情况下， > 背包容量为 j 时，能得到的最大价值** ⚠️ 注意三点： 1. **只考虑前 i 个物品**（后面的物品当不存在） 2. **背包容量固定是 j** 3. **这个格子一定是最优解** 也就是说： > **“每一个单元格，都是当前条件下的最优解”** 看图中第 0 行（i = 0）： > **不考虑任何物品** 那不管背包多大：`能装的最大价值 = 0` **每填一个格子，你只纠结一件事：** > 👉 **“当前这个物品，我要不要放？”** 只有两种选择，没有第三种。 #### 规则 1：如果放不下：只能不放 条件：`当前物品重量 > 当前背包容量` 那就：`dp[i][j] = dp[i-1][j]` 👉 **直接抄上一行** **例子：** - 当前物品：紫球（重 2） - 背包容量：1 2 > 1，放不下，所以：`dp[1][1] = dp[0][1] = 0` #### 规则 2：如果放得下：比较「放 vs 不放」 假设： - 当前是第 i 个物品 - 重量 = w - 价值 = v - 当前背包容量 = j 两种选择 ✅ 选择 1：不放 那就是：`价值 = dp[i-1][j]` ✅ 选择 2：放 放了之后： 1. 占用 w 的容量 2. 剩余容量 = j - w 3. 剩余容量里还能放什么？ 👉 **只能从前 i-1 个物品里选** 所以：`价值 = v + dp[i-1][j-w]`，**取最大值** ``` dp[i][j] = max( dp[i-1][j], // 不放 v + dp[i-1][j-w] // 放 ) ``` 也就是说， **“放进去划算还是不放划算”** #### 带你手算一个格子（非常重要） 我们看图中这一格，第 2 行、第 5 列 - 当前物品：水瓶（重 3，值 5） - 背包容量：5 1️⃣ 放得下吗？3 ≤ 5 ✔ 放得下 2️⃣ 不放的价值：`dp[1][5] = 3`（只放紫球） 3️⃣ 放的价值 - 剩余容量：5 - 3 = 2 - 查上一行第 2 列：`dp[1][2] = 3` - 加上水瓶的价值：`5 + 3 = 8` 4️⃣ 取最大值：`max(3, 8) = 8`，✔ 所以这一格是 **8** 为什么一定“查上一行”？因为这是 **0/1 背包**： > **每个物品只能用一次** 如果你查的是**当前行**，那就相当于允许一个物品用多次 那就变成了**完全背包**（另一个问题） 最后一格为什么是 9？右下角： - 背包容量 6 - 可以放： - 水瓶（3，5） - 西瓜（4，6） ❌ 超重 - 紫球（2，3） 最优组合是：`紫球 + 西瓜 = 2 + 4 = 6 价值 = 3 + 6 = 9` ✔ 所以答案是 **9** ### DP 表格回溯 > 目标： > **不仅知道最大价值是多少，还要知道“装了什么”** #### 1️⃣ 回溯的核心思想（一句话） > **看这一格的值，是不是“来自上面”，还是“来自左上 + 当前物品”** 换句话说： - 如果 **dp\[i\]\[j\] == dp\[i-1\]\[j\]** 👉 **第 i 个物品没选** - 如果 **dp\[i\]\[j\] != dp\[i-1\]\[j\]** 👉 **第 i 个物品选了** ⚠️ 注意： 前提是 `weight[i] ≤ j`，否则根本不可能选 #### 2️⃣ 回溯从哪里开始？ > **从右下角开始** `dp[n][W]` 也就是： - 考虑了所有物品 - 背包容量最大 - 得到的最终最优解 #### 3️⃣ 回溯规则（非常重要） 假设你现在在： `dp[i][j]` ##### 情况 A：dp\[i\]\[j\] == dp\[i-1\]\[j\] 说明： **不选第 i 个物品，也能达到当前最优值** 👉 所以：`第 i 个物品没选 i = i - 1 j 不变` ##### 情况 B：dp\[i\]\[j\] != dp\[i-1\]\[j\] 说明： **当前最优解必须选了第 i 个物品** 👉 所以：`第 i 个物品选了 j = j - weight[i] i = i - 1` #### 4️⃣ 用你那张图完整走一遍回溯 最终答案是：`dp[3][6] = 9` ##### 第一步：看 dp\[3\]\[6\] - dp\[3\]\[6\] = 9 - dp\[2\]\[6\] = 8 不相等 ⇒ **选了第 3 个物品（西瓜）** `j = 6 - 4 = 2 i = 2` ##### 第二步：看 dp\[2\]\[2\] - dp\[2\]\[2\] = 3 - dp\[1\]\[2\] = 3 相等 ⇒ **没选第 2 个物品（水瓶）** `i = 1 j = 2` ##### 第三步：看 dp\[1\]\[2\] - dp\[1\]\[2\] = 3 - dp\[0\]\[2\] = 0 不相等 ⇒ **选了第 1 个物品（紫球）** `j = 2 - 2 = 0 i = 0` #### 结束 最终选了： ✅ 物品 1（紫球） ✅ 物品 3（西瓜） ### DP 方程的真正含义 你现在看到的方程是： ``` dp[i][j] = max( dp[i-1][j], dp[i-1][j - w[i]] + v[i] ) ``` 我们来**逐句拆解人话含义**。 #### 1️⃣ dp\[i\]\[j\] 在“回答什么问题”？ > **在前 i 个物品里选， > 用容量 j 的背包， > 最多能赚多少钱？** #### 2️⃣ 为什么只有两种情况？ 因为 **0/1 背包的本质限制**： > 每个物品 > > - 要么选 > - 要么不选 不存在： - 选一半 - 选两次 #### 3️⃣ 为什么选了就一定是 dp\[i-1\]\[j-w\]？ 因为： - 你已经用了第 i 个物品一次 - 剩下只能从 **前 i-1 个物品里选** - 剩余容量是 `j - w[i]` 👉 **这不是技巧，是问题定义强制的** #### 4️⃣ 为什么取 max 就一定对？ 因为，**最优解一定来自“所有合法方案中价值最大的那个”**，而： - 所有合法方案 = 放 / 不放 两种情况 - max 就是在这两类里选最优 ### 三、怎么证明 0/1 背包具有「最优子结构」？ 这是理论核心，我们来**严谨但不装逼地讲清楚**。 #### 1️⃣ 什么叫最优子结构？ > 一个问题的最优解 > **可以由其子问题的最优解组合得到** #### 2️⃣ 对背包问题，子问题是什么？ 主问题：`前 i 个物品，容量 j 的最优解` 子问题： - 前 i-1 个物品，容量 j - 前 i-1 个物品，容量 j - w\[i\] #### 3️⃣ 正式证明思路（关键） 我们用 **反证法** ##### 假设： `S` 是问题 `(i, j)` 的一个最优解，且 **选了第 i 个物品** 那么： - S = {第 i 个物品} ∪ S' - S' 是在 **前 i-1 个物品**、**容量 j-w\[i\]** 下的一个解 ##### 关键一步（最重要） 如果： > S' 不是 `(i-1, j-w[i])` 的最优解 那么： - 存在另一个解 S''，价值更大 - 用 S'' + 第 i 个物品 👉 会得到比 S 更优的解 这 **与 S 是最优解矛盾** ##### 所以： > S' 必须是 `(i-1, j-w[i])` 的最优解 ✔ 这就证明了： > **最优解包含最优子解** #### 4️⃣ 不选第 i 个物品的情况同理 如果最优解没选第 i 个物品： - 那它就是 `(i-1, j)` 的最优解 - 否则同样可以构造更优解，产生矛盾 #### 5️⃣ 结论 > **0/1 背包问题具有最优子结构 > 所以可以用动态规划解决** ## 排序 ### 快速排序 快速排序采用分而治之的思想，首先从待排序序列中选取一个元素作为基准（pivot），通过一次划分操作将序列分为两部分，使得基准左侧的元素均不大于基准，右侧的元素均不小于基准；然后分别对左右两个子序列递归地进行快速排序，直到子序列规模为 1 或 0 为止。 ``` QuickSort(a, low, high): if low >= high then return pivot = Partition(a, low, high) QuickSort(a, low, pivot - 1) QuickSort(a, pivot + 1, high) ``` 【数据结构合集 - 快速排序(算法过程, 效率分析, 稳定性分析)】 https://www.bilibili.com/video/BV1y4421Z7hK/ ![PixPin_2026-01-15_20-49-17.png](https://gastigado.cnies.org/d/graduate/20260115204918509.webp) 最好：折半查找 ![PixPin_2026-01-15_20-51-25.png](https://gastigado.cnies.org/d/graduate/20260115205127920.webp) 最坏：pivot 取最小/最大值 **Partition (划分)** 函数的伪代码是必考的。你只会在纸上画表是不够的，必须能默写出类似下面的逻辑： - **输入**：数组 $A[p..r]$ - **逻辑**： 1. 选主元 $x = A[r]$ (通常选最后一个) 2. $i = p - 1$ 3. 遍历 $j$ 从 $p$ 到 $r-1$： 4. 如果 $A[j] \le x$，则 $i++$，交换 $A[i]$ 和 $A[j]$ 5. 最后交换 $A[i+1]$ 和 $A[r]$ 6. 返回 $i+1$ **建议：** 不要死记硬背具体的 C++ 代码，但要背熟上面这个**伪代码的逻辑步骤**，因为试卷是按行给分的。 ##### 2. 细节缺失：复杂度的“递推式” 往年试卷不仅问你复杂度是多少，还要求写出 **“复杂度的递推式及其闭式解”** 4。 - **你现在的状态**：记住了 $O(n \log n)$。 - **考试要求**：你可能需要写出： - **最好情况递推式：** $T(n) = 2T(n/2) + \Theta(n)$ - **最坏情况递推式：** $T(n) = T(n-1) + \Theta(n)$ （这是快排特有的，归并排序没有这个问题） ##### 3. 场景补充：最坏情况的触发条件 除了记忆“最坏是 $O(n^2)$”，你必须知道**什么时候**发生最坏情况。 - **常考简答题：** “在什么情况下快速排序会退化为冒泡排序/效率最低？” - **答案：** 当每次选择的 pivot 都是当前数组中的最小或最大元素（如已排序或逆序数组）时， 快速排序退化为 T(n)=T(n−1)+Θ(n)，时间复杂度为 Θ(n²)。 ![PixPin_2026-01-15_20-52-55.png](https://gastigado.cnies.org/d/graduate/20260115205257201.webp) ### 归并排序 ![PixPin_2026-01-15_21-01-57.png](https://gastigado.cnies.org/d/graduate/20260115210159193.webp) 核心思想：分而治之(Divide and Conquer) 1. 将数组一分为二 2. 对左右两部分分别进行归并排序 3. 合并两个有序数组 ![PixPin_2026-01-15_21-20-22.png](https://gastigado.cnies.org/d/graduate/20260115212024055.webp) ### 堆排序 【数据结构合集 - 堆与堆排序(算法过程, 效率分析, 稳定性分析)】 https://www.bilibili.com/video/BV1HYtseiEQ8/ ![PixPin_2026-01-16_10-24-17.png](https://gastigado.cnies.org/d/graduate/20260116102421024.webp) ![PixPin_2026-01-16_10-31-48.png](https://gastigado.cnies.org/d/graduate/20260116103151060.webp) ## 主定理 ![PixPin_2026-01-15_21-28-43.png](https://gastigado.cnies.org/d/graduate/20260115212844647.webp) ![PixPin_2026-01-15_21-28-53.png](https://gastigado.cnies.org/d/graduate/20260115212855461.webp) ## 时间复杂度 ![PixPin_2026-01-16_09-12-41.png](https://gastigado.cnies.org/d/graduate/20260116091243062.webp) ![PixPin_2026-01-16_09-15-04.png](https://gastigado.cnies.org/d/graduate/20260116091508933.webp) ## 蛮力法 ![PixPin_2026-01-16_09-26-47.png](https://gastigado.cnies.org/d/graduate/20260116092657720.webp) ## 分治法 ![PixPin_2026-01-16_09-32-56.png](https://gastigado.cnies.org/d/graduate/20260116093256892.webp) ## 算法基础 ### 一、算法基础（共 25 分） #### 一（1）给出 Knuth 的算法定义及其特征（5 分） ##### 【标准定义（必背）】 > **Knuth 对算法的定义：** > 算法是一个**有限的、确定的、可行的指令序列**，该序列对给定的输入产生相应的输出，并在有限步骤内终止。 ##### 【算法的五个特征（每点都要写）】 1. **输入（Input）** 算法有 0 个或多个输入。 2. **输出（Output）** 算法至少有 1 个输出。 3. **确定性（Definiteness）** 每一条指令含义明确、无二义性。 4. **有限性（Finiteness）** 算法在有限步骤后终止。 5. **可行性（Effectiveness）** 每一步操作都可以在有限时间内完成。 #### 一（2）给出渐近精确界 Θ 的定义及极限判定准则（5 分） ##### 【Θ 的定义（2–3 行最标准）】 > 若存在正常数 $c_1, c_2, n_0$，使得对所有 $n \ge n_0$，都有 > $$ > c_1 g(n) \le f(n) \le c_2 g(n) > $$ > 则称 $f(n)$ 的渐近精确界为 $\Theta(g(n))$。 ##### 【极限判定准则（必考）】 > 若 > $$ > \lim_{n \to \infty} \frac{f(n)}{g(n)} = c,\quad 0 < c < \infty > $$ > 则 > $$ > f(n) = \Theta(g(n)) > $$ ##### 📌 给分点提示 - 一定要出现 **“常数 c₁、c₂、n₀”** - 极限要写成 **正的有限常数** #### 一（3）画出基本 NP 完全问题归约树，并写出问题中文名（5 分） ##### 【经典 NP 完全归约链（你可以“画成文字”）】 ```text SAT ↓ 3-SAT ↓ CLIQUE（团问题） ↓ VERTEX COVER（顶点覆盖） ↓ INDEPENDENT SET（独立集） ``` ##### 【中文名称对应（一定要写）】 |英文|中文| |---|---| |SAT|布尔可满足性问题| |3-SAT|3-子句可满足性问题| |CLIQUE|团问题| |VERTEX COVER|顶点覆盖问题| |INDEPENDENT SET|独立集问题| #### 一（4）列出常见渐近函数的阶（含中文描述）（5 分） ### 【标准表（建议直接照写）】 |函数|阶|中文描述| |---|---|---| |1|O(1)|常数阶| |log n|O(log n)|对数阶| |n|O(n)|线性阶| |n log n|O(n log n)|线性对数阶| |n²|O(n²)|平方阶| |n³|O(n³)|立方阶| |2ⁿ|O(2ⁿ)|指数阶| |n!|O(n!)|阶乘阶| #### 一（5）手写多项式合并函数的大师定理（5 分） ##### 【Master 定理标准版】 设递推式为： $$ T(n) = aT\left(\frac{n}{b}\right) + f(n),\quad a \ge 1, b > 1 $$ ### 三种情况（一定要分条写） 1. **若** $f(n) = O(n^{\log_b a - \varepsilon})$ $$ 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})$ $$ T(n) = \Theta(f(n)) $$ ### 二、算法分析（共 25 分） #### 二（1）动态规划适用问题的两个特征（5 分） ##### 【标准答案】 1. **最优子结构** 原问题的最优解可以由子问题的最优解构成。 2. **重叠子问题** 在递归求解过程中，不同子问题会重复出现。 #### 二（2）说明贪心法与动态规划的不同（5 分） ##### 【标准对比答案】 |对比|贪心|动态规划| |---|---|---| |决策方式|局部最优|全局最优| |是否回溯|否|否（全面考虑）| |子问题|一般不重叠|有重叠| |结果|不一定最优|一定最优| ##### 【一句话总结（加分）】 > 贪心算法通过局部最优选择期望得到全局最优解，而动态规划通过系统地求解并保存子问题最优解来保证全局最优。 #### 二（3）Levenshtein 编辑距离定义及公式（5 分） ##### 【定义】 > 编辑距离是将一个字符串转换为另一个字符串所需的最少编辑操作次数，允许的操作包括插入、删除和替换。 ##### 【状态转移方程】 令 `dp[i][j]` 表示将 X 前 i 个字符变为 Y 前 j 个字符的最小操作数： $$ dp[i][j] = \min \begin{cases} dp[i-1][j] + 1 & (\text{删除}) \\ dp[i][j-1] + 1 & (\text{插入}) \\ dp[i-1][j-1] + cost & (\text{替换}) \end{cases} $$ #### 二（4）编辑距离 DP 伪代码及复杂度（5 分） ##### 【伪代码（简洁考试版）】 ```text for i = 0 to m: dp[i][0] = i for j = 0 to n: dp[0][j] = j for i = 1 to m: for j = 1 to n: if X[i] == Y[j]: dp[i][j] = dp[i-1][j-1] else dp[i][j] = 1 + min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) ``` ##### 【复杂度】 - 时间复杂度：$O(mn)$ - 空间复杂度：$O(mn)$ #### 二（5）矩阵链乘法 DP 方程及伪代码（5 分） ##### 【DP 方程】 $$ m[i][j] = \begin{cases} 0, & i=j \\ \min_{i\le k1 \end{cases} $$ **闭式解：** $T(n) = O(n^{\log_2 3}) \approx O(n^{1.58})$ ## 3. 快速排序基本思想、复杂度 **基本思想：** 从待排序的数列中选定一个作为枢纽元素的数字，然后采用一种分区算法，将枢纽元素排到正确位置上，使其前元素比它小，其后元素比它大。其他元素划分为两个区，然后再用分治策略利用上述过程求解前后两个分区，其直到分区中仅剩不超过 1 个元素。 **复杂度：** * 最坏复杂度：$O(n^2)$ * 平均/最好：$O(n \log n)$ ## 4. 多项式合并函数下的大师定理 当 $T(n) = aT(n/b) + f(n)$ 中 $f(n) = O(n^d)$ 时，大师定理可简化： 对常数 $a \ge 1, b > 1, d \ge 0$，有 $T(n) = aT(n/b) + O(n^d)$，则 $T(n)$ 有如下闭式解： $$ T(n) = \begin{cases} O(n^d) & d > \log_b a \\ O(n^d \log n) & d = \log_b a \\ O(n^{\log_b a}) & d < \log_b a \end{cases} $$ ## 5. Knuth 的算法定义及特性 算法是一组有穷规则的集合，这些规则给出了求解特定类型问题的运算序列。它具有 5 个重要特性，即： 1. 有穷性 (Finiteness) 2. 确定性 (Definiteness) 3. 有效性 (Effectiveness) 4. 输入 (Input) 5. 输出 (Output) ## 6. Euclid GCD 手算表格 | No | a | b | q=$\lfloor a/b \rfloor$ | r | | :--- | :--- | :--- | :--- | :--- | | 1 | 98 | 56 | 1 | 42 | | 2 | 56 | 42 | 1 | 14 | | 3 | 42 | 14 | 3 | 0 | | 4 | 14 | 0 | | | ## 7. 适应于动态规划方法求解的问题的 2 个特征 1. 最优子结构性质 (Optimal Substructure) 2. 子问题重叠性 (Overlapping Subproblems) ## 8. Levenshtein 编辑距离的定义及公式表达 **定义：** 两个字符串间的编辑距离是指将一个字符串变换为另一个字符串的基本编辑操作数。这里的编辑操作指的是对单个字符的**插入**、**删除**和**替换** 3 种基本编辑操作。 **公式：** $$ lev_{a,b}(i, j) = \begin{cases} \max(i, j) & \min(i, j) = 0 \\ \min \begin{cases} lev_{a,b}(i-1, j) + 1 \\ lev_{a,b}(i, j-1) + 1 \\ lev_{a,b}(i-1, j-1) + \delta(a_i, b_j) \end{cases} & \text{else} \end{cases} $$ （注：公式中若 $a_i \neq b_j$ 则 $\delta=1$，否则 $\delta=0$） ## 9. 给出 Levenshtein 编辑距离的 DP 算法伪代码、复杂度 **复杂度：** $O(mn)$ **伪代码：** ```text Function LevenshteinDistance(S1, S2) m = length(S1), n = length(S2) Create DP[m+1][n+1] // Initialization From For i = 0 to m: DP[i][0] = i For j = 0 to n: DP[0][j] = j // Main Loop For i = 1 to m: For j = 1 to n: If S1[i-1] == S2[j-1]: cost = 0 else: cost = 1 DP[i][j] = min( DP[i-1][j] + 1, // Deletion DP[i][j-1] + 1, // Insertion DP[i-1][j-1] + cost // Substitution ) return DP[m][n] ``` ## 10. 0-1 背包问题的形式化定义 给定 $n$ 个重量分别为 $w_1, w_2, \dots, w_n$，价值分别为 $v_1, v_2, \dots, v_n$，且不可分割的物品及一个容量 $W$ 的背包，问装入哪些物品可以获得最大的价值？ ## 11. 0-1 背包问题 DP 算法子问题的定义及 DP 方程 **子问题定义：** 将前 $i$ ($0 \le i \le n$) 个物品装入容量为 $j$ ($0 \le j \le W$) 的背包，问最大可以获得多少价值？ **DP 方程：** $$ V(i, j) = \begin{cases} 0 & i=0 \text{ or } j=0 \\ V(i-1, j) & w_i > j, 1 \le i \le n \\ \max \{ V(i-1, j), V(i-1, j-w_i) + v_i \} & w_i \le j, 1 \le i \le n \end{cases} $$ **复杂度：** $T(n, W) = O(nW)$ --- **0-1 背包问题的动态规划算法的伪代码** ```text 1. int Dp0-1Knapsack(int n, int W, int *w, int *v) 2. { 3. for (int i = 1; i <= n; i++) 4. for (int j = 1; j <= W; j++) 5. if (j < w[i-1]) 6. V[i][j] = V[i-1][j]; 7. else if (V[i-1][j] >= V[i-1][j-w[i-1]] + v[i-1]) // 这里笔记有一处判断逻辑 8. V[i][j] = V[i-1][j]; 9. else 10. V[i][j] = V[i-1][j-w[i-1]] + v[i-1]; 11. 11. // Backtracking to find items 12. int j = W; 13. for (int i = n; i > 0; i--) 14. if (V[i][j] == V[i-1][j]) 15. x[i] = 0; 16. else { 17. x[i] = 1; j -= w[i-1]; 18. } 19. return V[n][W]; 20. } ``` ## 12. 设有价值为 5, 8, 4, 3，重量为 4, 6, 5, 4 和容量为 10 的背包，设计并给出 DP 计算的手写表 物品/容量 ($W=10$)： * $i=1: w=4, v=5$ * $i=2: w=6, v=8$ * $i=3: w=5, v=4$ * $i=4: w=4, v=3$ **DP 表格 (部分还原)：** | $i$ \ $j$ | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | | :-------- | :-- | :-- | :-- | :-- | :-- | :-- | :-- | :-- | :-- | :-- | :-- | | **0** | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | **1** | 0 | 0 | 0 | 0 | 5 | 5 | 5 | 5 | 5 | 5 | 5 | | **2** | 0 | 0 | 0 | 0 | 5 | 5 | 8 | 8 | 8 | 8 | 13 | | **3** | 0 | 0 | 0 | 0 | 5 | 5 | 8 | 8 | 8 | 9 | 13 | | **4** | 0 | 0 | 0 | 0 | 5 | 5 | 8 | 8 | 8 | 9 | 13 | **结论：** 最优解是物品 2 和 4 (注：根据价值 13 推算，应为物品 1 和 2，但笔记写的是 2 和 4)，最优解值 13。 ## 13. 给出 RSA 算法的主流程代码，说明其不可攻破性和可行性，复杂度 **不可攻破性：** 基于大整数分解的困难性。 **可行性：** **RSA 的安全性基于大整数分解的困难性。在已知公钥 $(e, n)$ 的情况下，想要推导出私钥 $d$，必须对 $n$ 进行因式分解，这在计算上是不可行的（Computationally Infeasible）。而 RSA 的加密和解密操作利用模幂运算，在计算上是高效可行的。**” **复杂度：** $O(\ln n)$ (注：笔记手写标注) **流程：** 1. 取两个素数 $p$ 和 $q$。Miller-Rabin 素性测试算法。 2. 计算 $n = pq$, $\phi(n) = (p-1)(q-1)$。大整数乘法。 3. 取一个与偶数 $\phi(n)$ 互素的数 $e$。Euclid GCD 算法。 4. 计算 $e \pmod{\phi(n)}$ 的乘法逆元 $d$。扩展欧几里得算法。 5. 置 $P=(e, n)$ 为 RSA 公钥， $S=(d, n)$ 为 RSA 私钥。 6. 对 $0 \le P \le n-1$ 加密，$C = P^e \mod n$。模幂运算的反复平方算法。 7. 对 $C$ 解密，$P = C^d \mod n$。模幂运算的反复平方算法。 ## 14. 设 p=3, q=11, 进行 RSA 运算 计算 $n, \phi(n)$，确定与 $\phi(n)$ 互素的 $e$，计算乘法逆元 $d$，然后用公钥 $(e, n)$ 和私钥 $(d, n)$ 对 30 进行加密和解密。 1. $n = p \times q = 33$ 2. $\phi(n) = (p-1)(q-1) = 20$ 3. 令 $e = 7$ 4. $\gcd(e, \phi(n)) = 1$ **扩展欧几里得求逆元 $d$：** | No | $a=e$ | $b=\phi(n)$ | $q=\lfloor a/b \rfloor$ | $r$ | | :--- | :--- | :--- | :--- | :--- | | 1 | 7 | 20 | 0 | 7 | | 2 | 20 | 7 | 2 | 6 | | 3 | 7 | 6 | 1 | 1 | | 4 | 6 | 1 | 6 | 0 | | 5 | 1 | 0 | | | **逆元推导过程：** $$ \begin{aligned} \therefore & a_5 x_1 + b_5 x_0 = 1 \\ & b_4 x_1 + (a_4 - q_4 b_4) x_0 = 1 \\ & (a_3 - q_4 b_3) x_1 = 1 \\ \therefore & 1b_2 - 6(a_2 - q_2 b_2) = 1 \\ & -6a_2 + 3b_2 = 1 \\ & -6b_1 + 3(a_1 - q_1 b_1) = 1 \\ & 3a_1 - 6b_1 = 1 \end{aligned} $$ 即乘法逆元 $d = 3$。 **加密与解密运算：** 公钥 $(7, 33)$，私钥 $(3, 33)$ **加密：** $C = m^e \mod n = 30^7 \mod 33$ | $i$ | 2 | 1 | 0 | | :--- | :--- | :--- | :--- | | $b$ | 1 | 1 | 1 | | $d^2$ | 1 | $900 \to 9$ | $36 \to 3$ | | $d^2 \mod n$ | 1 | 9 | 3 | | $d \cdot a$ | 30 | 270 | 90 | | $d \cdot a \mod n$ | 30 | 6 | 24 | **即 $C=24$** **解密：** $m = C^d \mod n = 24^3 \mod 33$ ($a=24, b=3, d=1, n=33$) | $i$ | 1 | 0 | | :--- | :--- | :--- | | $b$ | 1 | 1 | | $d^2$ | 1 | $576 \to 15$ | | $d \cdot a$ | 24 | 360 | | $d \cdot a \mod n$ | 24 | 30 | **即 $m=30$** ## 15. 归并算法基本思想、伪代码 **Two Way Merge 基本思想：** 1. 顺次比较左右两个子数组中的元素 2. 将比较小者放入临时数组 3. 最后将左或右两个子数组中剩余元素复制到临时数组 4. 将临时数组中的元素复制回原数组 **伪代码 (TwoWayMerge)：** * **输入**：数组 $a$, $p \sim q$ 和 $q+1 \sim r$ 的元素已排好序的数组 * **输出**：$p \sim r$ 的元素已排好的数组 $a$ ```text 1. TwoWayMerge(a, p, q, r, b) 2. i = p, j = q + 1, k = p 3. for k = p to r 4. if (i <= q and (j > r or a[i] <= a[j])) 5. b[k] = a[i]; i = i + 1 6. else 7. b[k] = a[j]; j = j + 1 8. for k = p to r 9. a[k] = b[k] ``` 复杂度 $O(n)$。 **归并排序 (MergeSort) 基本思想：** * **分解：** 将排序数组分解为左右两个大小不重叠的子数组。 * **解决：** 当子问题规模大于 1 时递归；当为 1 时则为平凡有序数组，直接返回。 * **合并：** 将两个有序数组合并为一个有序数组。 **伪代码 (MergeSort)：** * **输入**：$n$ 个元素的数组 $a$ * **输出**：排序的 $a$ ```text 1. MergeSort(a, low, high) 2. if low = high then return 3. mid = (low + high) / 2 4. MergeSort(a, low, mid) 5. MergeSort(a, mid+1, high) 6. TwoWayMerge(a, low, mid, high) ``` ## 16. NP 难题 令 $\pi$ 是一个判定性问题，如果对 NP 问题中的每个问题 $\pi' \in NP$ 都有 $\pi' \le_P \pi$，则称判定性问题 $\pi$ 是一个 NP 难题 (NP-Hard)。 ## 17. NP 完全问题 令 $\pi$ 是一个判定性问题，如果 $\pi \in NP$，且对 NP 中的每个问题 $\pi' \in NP$ 都有 $\pi' \le_P \pi$，则称判定性问题 $\pi$ 是一个 NP 完全问题 (NPC)。 ## 18. NP 完全问题归约树 ```mermaid graph TD A[布尔电路可满足性问题] --> B[布尔可满足性问题 SAT] B --> C[3-CNF 可满足性问题] C --> D[团问题] D --> E[顶点覆盖问题] E --> F[子集和问题] C --> G[哈密尔顿回路问题] G --> H[旅行商问题 TSP] %% 样式调整（可选，为了更美观） style A fill:#f9f,stroke:#333,stroke-width:2px style C fill:#bbf,stroke:#333,stroke-width:2px ``` --- # 第三部分：专题详解 --- # 算法设计补考速成 考点 ## RSA 算法 1. 基本原理：时间复杂度、可行性、不可攻破性 2. 密钥生成 3. 扩展欧几里得算法（含表格） 4. 反复平方算法（手画表格） ## 算法基础 1. 渐近时间复杂度：$\Theta$ 精确界、$O$ 上界、$\Omega$ 下界的定义及极限判定；常见渐近函数的阶和中文描述 2. 大师定理：手写多项式合并函数的大师定理公式 3. NP 和 NP 完全定理：P、NP、NP-Hard、NPC 的定义关系，归约的意义，常见 NPC 中文名称；经典归约链、归约树大致结构 4. 算法定义 / Knuth 对算法的定义 ## 分治排序算法 ### Karatsuba 大整数乘法 推导公式、复杂度分析。 #### 核心思想 将原本 4 次的乘法降低到 3 次： $$ X = A \cdot 10^{n/2} + B, \qquad Y = C \cdot 10^{n/2} + D $$ $$ X \cdot Y = AC \cdot 10^n + (AD + BC) \cdot 10^{n/2} + BD $$ 其中共有四次乘法：$AC, AD, BC, BD$。 将 $$ AD + BC $$ 替换为 $$ (A+B)(C+D) - AC - BD $$ 于是只需要三次乘法。 #### 递推式与时间复杂度 $$ T(n) = 3T(n/2) + O(n) $$ 根据大师定理：$a=3, b=2, d=1$，且 $3 > 2^1$，故 $$ T(n)=O\left(n^{\log_2 3}\right) \approx O(n^{1.585}) $$ 对比朴素乘法 $O(n^2)$，属于典型分治优化。 ### 归并 / 快速排序 要求：会写伪代码、会分析时间复杂度。 - 归并排序的 Merge 合并逻辑及伪代码 - 手算执行过程、闭解式 - 时间复杂度递推式 归并排序 / 快速排序常写为： $$ T(n) = 2T(n/2) + \Theta(n) $$ ### 二叉最大堆 - 节点上移操作（shift up）的基本思想 - 伪代码 - 复杂度：$O(\log n)$ - 会画树形演变过程 ### 回溯法 VS 分支限界法 - N 皇后问题 ## 动态规划与贪心算法 ### 0/1 背包与动态规划 1. 概念与证明：0/1 背包形式化定义、DP 子问题及动态规划方程，证明最优子结构的正确性 2. 手算表：给定一组物品重量、价值和背包容量，画出 DP 计算矩阵表，并通过表格回推最优解（即哪些物品被装入） 3. 算法对比：说明贪心算法与动态规划的区别；贪心具有贪心选择策略，DP 具有重叠子问题。说明为什么 0/1 背包不能用贪心算法求解（需举例） 4. 0/1 背包的 DP 方程、伪代码、复杂度、手算表 ### Levenshtein 编辑距离与矩阵链相乘 1. Levenshtein 编辑距离：定义、公式表达、DP 算法伪代码、时间复杂度 2. 矩阵链相乘：动态规划方程及伪代码 ### 动态规划与贪心法的不同 ## RSA 加密算法 ### 加密过程 1. 选择一对不相等且足够大的质数 $p, q$ 2. 计算 $$ n = p \times q $$ 3. 计算 $n$ 的欧拉函数 $$ \varphi(n) = (p-1)(q-1) $$ 4. 选一个与 $\varphi(n)$ 互质的整数 $e$，满足 $$ 1 < e < \varphi(n) $$ 5. 计算出 $e$ 对于 $\varphi(n)$ 的模反元素 $d$，使得 $$ de \bmod \varphi(n) = 1 $$ 6. 公钥 $$ KU = (e, n) $$ 7. 私钥 $$ KR = (d, n) $$ ### 模反元素 $d$ 如果 $e$ 和 $\varphi(n)$ 互质，那么一定存在整数 $d$，使得 $ed - 1$ 能被 $\varphi(n)$ 整除，也即： $$ ed \equiv 1 \pmod{\varphi(n)} $$ 等价表达： $$ ed - 1 = k\varphi(n) $$ $$ ed \bmod \varphi(n) = 1 $$ $$ ed \equiv 1 \pmod{\varphi(n)} $$ 例如：$3$ 和 $11$，有 $$ 3 \times 4 - 1 = 11 $$ 故 $d=4$。更一般地，$4 + k \cdot 11$ 都可以视为一个解，因此 $d + k\varphi(n)$ 都是 $e$ 的模反元素。通常取最小正整数解，便于计算。 明文 $M$、密文 $C$ 的加解密公式： $$ M^e \bmod n = C $$ $$ C^d \bmod n = M $$ ## RSA 加密算法（例题） ### 密钥生成与加解密 设： $$ p=5, \quad q=11, \quad e=3 $$ 则 $$ n=pq=5\times 11=55 $$ $$ \varphi(n)=(p-1)(q-1)=(5-1)(11-1)=4\times 10=40 $$ 求 $d$： $$ 3d \equiv 1 \pmod{40} $$ 可得 $$ d=27 $$ 于是： - 公钥：$(n,e)=(55,3)$ - 私钥：$(n,d)=(55,27)$ 给定明文 $$ m=14 $$ 加密公式： $$ C = m^e \bmod n = 14^3 \bmod 55 $$ 原稿后续用快速幂 / 取模化简演算： $$ 14^2 = 196 \equiv 31 \pmod{55} $$ $$ 14^3 \equiv 31 \times 14 = 434 \equiv 49 \pmod{55} $$ 故 $$ C = 49 $$ 再解密： $$ 49^{27} \bmod 55 = 14 $$ 手稿中给出了连乘取模表，最终得到 $$ m=14 $$ ## 扩展欧几里得算法求逆元 使用推广 Euclid 算法求 $67 \bmod 119$ 的逆元。 即求整数 $x$，使得 $$ 67x \equiv 1 \pmod{119} $$ 等价于求整数解： $$ 67x + 119k = 1 $$ 只要 $$ \gcd(67,119)=1 $$ 就有整数解。扩展 Euclid 不仅判断两个数是否互质，还能构造出这样的 $(x,y)$。 ### 辗转相除法求最大公约数 $$ 119 = 1\times 67 + 52 $$ $$ 67 = 1\times 52 + 15 $$ $$ 52 = 3\times 15 + 7 $$ $$ 15 = 2\times 7 + 1 $$ $$ 7 = 1\times 1 + 0 $$ 最后一个非零余数是 $1$，因此 $$ \gcd(67,119)=1 $$ 所以逆元存在。 注意：不是所有的模数都有逆元。只有当 $$ \gcd(a,m)=1 $$ 时，$a$ 才在模 $m$ 下有逆元。 ### 回代法求逆元 目标是把 $1$ 表示成 $67$ 和 $119$ 的线性组合。 由 $$ 1 = 15 - 2\times 7 $$ 又因为 $$ 7 = 52 - 3\times 15 $$ 代入得 $$ 1 = 15 - 2(52 - 3\times 15) $$ $$ = 7\times 15 - 2\times 52 $$ 再由 $$ 15 = 67 - 1\times 52 $$ 得 $$ 1 = 7(67 - 52) - 2\times 52 $$ $$ = 7\times 67 - 9\times 52 $$ 再由 $$ 52 = 119 - 67 $$ 得 $$ 1 = 7\times 67 - 9(119 - 67) $$ $$ = 16\times 67 - 9\times 119 $$ 于是 $$ 1 = 16\times 67 + (-9)\times 119 $$ 所以 $$ 16\times 67 \equiv 1 \pmod{119} $$ 故 $67$ 在模 $119$ 下的逆元为： $$ 16 $$ ## 反复平方算法 目的：用 $O(\log n)$ 次运算代替 $O(n)$ 次连乘。 计算： $$ 14^3 \bmod 55 $$ ### 指数二进制化 $$ 3=(11)_2=2^1+2^0 $$ ### 反复平方（每一步取模） $$ 14^{2^0} \equiv 14 \pmod{55} $$ $$ 14^2 = 196 \equiv 31 \pmod{55} $$ 即： $$ 14^{2^1} \equiv 31 \pmod{55} $$ ### 按二进制位为 1 的幂相乘 $$ 14^3 = 14^{2^1} \cdot 14^{2^0} $$ $$ 14^3 \equiv 31\times 14 = 434 \equiv 49 \pmod{55} $$ ### 原理模板 设 $$ n = \sum b_i 2^i, \qquad b_i \in \{0,1\} $$ 则 $$ a^n = \prod_i a^{b_i 2^i} $$ 并利用模运算性质： $$ (ab \bmod m)=((a\bmod m)(b\bmod m))\bmod m $$ 因此每一步都可以先取模，防止数字过大。 ### 反复平方算法（表格解法） 计算： $$ 10^{27} \bmod 55 $$ 因为 $$ 27=(11011)_2=16+8+2+1 $$ 可整理为下表： | $i$ | $e_i$ | $10^{2^i} \bmod 55$ | 累积结果 | | ---- | ----: | -------------------: | ---------------------: | | 0 | 1 | 10 | $1\times 10=10$ | | 1 | 1 | $10^2=100\equiv 45$ | $10\times 45\equiv 10$ | | 2 | 0 | $45^2=2025\equiv 45$ | 不变 | | 3 | 1 | $45^2\equiv 45$ | $10\times 45\equiv 10$ | | 4 | 1 | $45^2\equiv 45$ | $10\times 45\equiv 10$ | 因此： $$ 10^{27} \equiv 10 \pmod{55} $$ ### RSA 算法的时间复杂度 RSA 算法的加密与解密主要计算为模指数运算。采用快速幂算法时，其时间复杂度为 $$ O(\log n) $$ 次模运算。 ### 计算可行性与不可攻破性 #### 可行性 已知 $p,q$ 时，就能轻松算出 $\varphi(n)$，再用扩展 Euclid 算法求 $d$；模指数运算可用反复平方算法。因此 RSA 的密钥生成和加解密过程均可在多项式时间内完成，计算上可行。 #### 不可攻破性 已知 $n$ 而不知道 $p,q$ 时，无法直接得到 $\varphi(n)$，也无法求出 $d$。在现有计算能力和已知算法条件下，大整数因式分解在计算上不可行，因此 RSA 具有不可攻破性。 ## RSA 计算大题例题 设 $$ p=3, \quad q=11, \quad m=30 $$ 进行 RSA 计算：先求 $n$、$\varphi(n)$，确定与 $\varphi(n)$ 互素的 $e$，再计算乘法逆元 $d$，然后用公钥 $(e,n)$ 和私钥 $(d,n)$ 对 $30$（明文）进行加密和解密。 ### 参数计算 $$ n=pq=33 $$ $$ \varphi(n)=(p-1)(q-1)=20 $$ 选取 $$ e=7 $$ 因为 $10, n_0$，使得当 $n\ge n_0$ 时， $$ 0 \le f(n) \le cg(n) $$ 则记作 $$ f(n)=O(g(n)) $$ 含义：$f(n)$ 的增长速度不超过 $g(n)$ 的常数倍，即至多与 $g(n)$ 同阶，上界为 $g(n)$。 #### 大 $\Omega$：下界 若存在正常数 $c>0, n_0$，使得当 $n\ge n_0$ 时， $$ 0 \le cg(n) \le f(n) $$ 则记作 $$ f(n)=\Omega(g(n)) $$ 含义：$f(n)$ 增长速度至少和 $g(n)$ 一样快，即下界为 $g(n)$。 #### 大 $\Theta$：渐进精确界 若存在正常数 $c_1,c_2>0,n_0$，使得当 $n\ge n_0$ 时， $$ 0 \le c_1 g(n) \le f(n) \le c_2 g(n) $$ 则记作 $$ f(n)=\Theta(g(n)) $$ 含义：$f(n)$ 与 $g(n)$ 在无穷远处只差常数倍，增长速度完全同阶。中文常说：与 $g(n)$ 同阶，精确阶为 $g(n)$。 #### 极限判定 令 $$ L=\lim_{n\to\infty}\frac{f(n)}{g(n)} $$ - 若 $01$ 是常数，$f(n)$ 是一个函数， $$ T(n)=aT\left(\frac{n}{b}\right)+f(n) $$ 对比 $f(n)$ 与 $n^{\log_b a}$： 1. 若 $$ f(n)=O\left(n^{\log_b a-\varepsilon}\right), \quad \varepsilon>0 $$ 则 $$ T(n)=\Theta\left(n^{\log_b a}\right) $$ 2. 若 $$ f(n)=\Theta\left(n^{\log_b a}\right) $$ 则 $$ T(n)=\Theta\left(n^{\log_b a}\log n\right) $$ 3. 若 $$ f(n)=\Omega\left(n^{\log_b a+\varepsilon}\right), \quad \varepsilon>0 $$ 且对充分大的 $n$ 满足正则条件 $$ af(n/b)\le cf(n), \quad c<1 $$ 则 $$ T(n)=\Theta(f(n)) $$ #### 例 1 $$ T(n)=9T(n/3)+n $$ 有 $a=9,b=3,f(n)=n$，而 $$ n^{\log_3 9}=n^2 $$ 所以 $$ T(n)=\Theta(n^2) $$ #### 例 2 $$ T(n)=T\left(\frac{2}{3}n\right)+1 $$ 手稿中写法等价于 $a=1,b=3/2,f(n)=1$，因此 $$ T(n)=\Theta(\log n) $$ #### 例 3 $$ T(n)=3T(n/4)+n\log n $$ 其中 $$ n^{\log_4 3}\approx O(n^{0.793}) $$ 而 $n\log n$ 多项式意义上更大，并满足正则条件，因此 $$ T(n)=\Theta(n\log n) $$ #### 例 4 $$ T(n)=2T(n/2)+n\log n $$ 此时 $n^{\log_2 2}=n$，而 $f(n)=n\log n$ 比 $n$ 大一个对数因子，不属于标准三种情形中的多项式差距，手稿注明：**不适用于基础版大师定理**。 ### 大 $O$ 记法定义及其极限判别准则 对于给定的复杂函数 $T(n)$，若存在两个正常数 $C$ 和 $n_0$，以及函数 $\tau(n)$，使得当 $n\ge n_0$ 时有 $$ T(n)\le C\tau(n) $$ 则称 $$ T(n)=O(\tau(n)) $$ 并且 $$ T(n)=O(\tau(n)) \iff 0 \le \lim_{n\to\infty}\frac{T(n)}{\tau(n)} < +\infty $$ ### NP、NPH、NPC - **NP**：答案如果给你，能很快验证对不对 - **NP-Hard**：至少和 NP 中最难的问题一样难 - **NP-Complete**：既是 NP，又是 NP-Hard - 记法： $$ NPC = NP \cap NPH $$ #### 判定式定义 1. **NP 问题**：如果一个判定问题的解可以在多项式时间内验证，则属于 NP。 2. **NPH 问题**：如果一个问题 $\pi$ 满足：对任意 $\pi'\in NP$，都有 $\pi'\le_p \pi$，则称 $\pi$ 为 NPH。也就是 NP 中任何问题都可以多项式时间归约到它，因此它至少和所有 NP 问题一样难。 3. **NPC 问题**：如果一个问题 $\pi$ 满足： - $\pi \in NP$ - 对任意 $\pi'\in NP$，都有 $\pi'\le_p \pi$ 则称 $\pi$ 为 NPC。 也就是说，它的答案能快速验证，属于 NP；又足够难，属于 NPH，所以是 NP 里最难的一批问题。 若能解决问题 $\pi$，那么把其他问题多项式时间转换为 $\pi$ 的过程，也就能一并解决。 #### 经典归约链 手稿中的归约链为： $$ \text{布尔电路可满足性问题} \to SAT \to 3\text{-}SAT $$ 再由 $3$-SAT 归约到其他经典问题，例如： - 团问题 $\to$ 顶点覆盖问题 $\to$ 子集和 / 覆盖类问题（手稿此处为示意） - 哈密尔顿回路问题 $\to$ 旅行商问题（TSP） ## 分治排序算法 ### Karatsuba 大数乘法 把两个长整数 $x,y$ 折半： $$ x=x_1B^m+x_0 $$ $$ y=y_1B^m+y_0 $$ 则 $$ xy=(x_1B^m+x_0)(y_1B^m+y_0) $$ 展开为 $$ xy=x_1y_1B^{2m}+(x_1y_0+x_0y_1)B^m+x_0y_0 $$ 记 $$ z_2=x_1y_1, \qquad z_1=x_1y_0+x_0y_1, \qquad z_0=x_0y_0 $$ 则仍是四次乘法。 进一步将 $$ z_1=(x_1+x_0)(y_1+y_0)-x_1y_1-x_0y_0 = z_3-z_2-z_0 $$ 只需要三次乘法。 递推式： $$ T(n)=3T(n/2)+cn+d $$ 因此 $$ T(n)=\Theta(n^{\log_2 3})\approx \Theta(n^{1.585}) $$ #### 伪代码 ```text 输入：两个 n 位正整数 X 和 Y 输出：X 和 Y 的乘积 1. multiplyK(X, Y) 2. n <- X 和 Y 的位数 3. if n = 1 return X * Y 4. x1, x0 <- X 的高 n/2 位和低 n/2 位 5. y1, y0 <- Y 的高 n/2 位和低 n/2 位 6. z2 <- multiplyK(x1, y1) 7. z0 <- multiplyK(x0, y0) 8. z3 <- multiplyK(x1 + x0, y1 + y0) 9. return z2 * 10^n + (z3 - z2 - z0) * 10^(n/2) + z0 ``` ### 二叉最大堆 给定序列： $$ [40,55,49,73,12,27,98,81,64,36] $$ 要求：给出由该序列构建大根堆的过程；根节点比子节点大。 从 $\lfloor n/2 \rfloor = 10/2 = 5$​ 开始，自底向上调整。 ![image-20260322221908698](https://gastigado.cnies.org/d/graduate/image-20260322221908698.webp) #### 初始完全二叉树 ```mermaid graph TD A40((40)) --> A55((55)) A40 --> A49((49)) A55 --> A73((73)) A55 --> A12((12)) A49 --> A27((27)) A49 --> A98((98)) A73 --> A81((81)) A73 --> A64((64)) A12 --> A36((36)) ``` #### 调整后的大根堆 ```mermaid graph TD R98((98)) --> R81((81)) R98 --> R49((49)) R81 --> R73((73)) R81 --> R36((36)) R49 --> R27((27)) R49 --> R40((40)) R73 --> R55((55)) R73 --> R64((64)) R36 --> R12((12)) ``` #### 小根堆中依次插入数据 $4, 2, 5, 8, 3, 6, 10, 1$ ##### 插入 4 ```mermaid graph TD A4((4)) ``` ##### 插入 2 ```mermaid graph TD B2((2)) --> B4((4)) ``` ##### 插入 5 ```mermaid graph TD C2((2)) --> C4((4)) C2 --> C5((5)) ``` ##### 插入 8 ```mermaid graph TD D2((2)) --> D4((4)) D2 --> D5((5)) D4 --> D8((8)) ``` ##### 插入 3 ```mermaid graph TD E2((2)) --> E3((3)) E2 --> E5((5)) E3 --> E8((8)) E3 --> E4((4)) ``` ##### 插入 6 ```mermaid graph TD F2((2)) --> F3((3)) F2 --> F5((5)) F3 --> F8((8)) F3 --> F4((4)) F5 --> F6((6)) ``` ##### 插入 10 ```mermaid graph TD G2((2)) --> G3((3)) G2 --> G5((5)) G3 --> G8((8)) G3 --> G4((4)) G5 --> G6((6)) G5 --> G10((10)) ``` ##### 插入 1（最终） ```mermaid graph TD H1((1)) --> H2((2)) H1 --> H5((5)) H2 --> H3((3)) H2 --> H4((4)) H3 --> H8((8)) H5 --> H6((6)) H5 --> H10((10)) ``` ### 回溯法 VS 分支限界法：N 皇后问题 回溯法和分支限界法通过约束条件和限界条件对状态空间树进行剪枝，使得一部分分支不需搜索，从而对很多问题实例都能改进穷举法的搜索效率。 - 回溯法：在 DFS 上进行 - 分支限界法：在 BFS 基础上进行 N 皇后问题中，回溯法通过判断两个皇后不能在同一列上，即 $x[i] \ne x[j]$，并且不能在同一条对角线上，即 $$ |i-j| \ne |x[i]-x[j]| $$ 来实现剪枝，从而改进穷举算法。 手稿示例输入输出： $$ n=6 $$ 输出三组结果： - 246135 - 362514 - 415263 并注明：第一个位于第二列，第二行位于第四列。 ## 动态规划与贪心算法 ### 0/1 背包和动态规划 动态规划适用于： 1. **最优子结构**：原问题最优解可以由子问题最优解构成 2. **重叠子问题**：在递归求解过程中，不同子问题会重复出现 #### 贪心与动态规划的不同 ##### 贪心 - 局部最优 - 不回溯 - 子问题一般不重叠 - 结果不一定最优 ##### 动态规划 - 全局最优 - 不回溯 - 子问题重叠 - 结果一定最优 #### 0/1 背包状态定义 令第 $i$ 个物品重量为 $w_i$，价值为 $v_i$。 设 $$ dp[i][j] $$ 表示前 $i$ 个物品、背包容量为 $j$ 时的最大价值。 状态转移： $$ dp[i][j] = \begin{cases} dp[i-1][j], & j < w_i \\ \max\{dp[i-1][j],\; dp[i-1][j-w_i]+v_i\}, & j \ge w_i \end{cases} $$ 手稿右下角还写有一维压缩式的提示，形式可写为： $$ dp[i][j] = \max\bigl(dp[i-1][j],\; dp[i-1][j-w_i] + v_i\bigr) $$ ### Levenshtein 编辑距离与矩阵链相乘 两个字符串间的编辑距离，是指把一个字符串变成另一个字符串的基本操作数。这里的基本编辑操作包括： - 插入 - 删除 - 替换 #### 递推定义 设 $a,b$ 为两个字符串，$lev_{a,b}(i,j)$ 表示：字符串 $a$ 的前 $i$ 个字符变成字符串 $b$ 的前 $j$ 个字符的最小编辑距离。 边界： $$ \min(i,j)=0 $$ 更准确地说： - 若 $i=0$，表示空串到 $b$ 的前 $j$ 个字符，需要连续插入 $j$ 次 - 若 $j=0$，表示 $a$ 的前 $i$ 个字符到空串，需要连续删除 $i$ 次 定义代价函数： $$ \delta(a_i,b_j)= \begin{cases} 0, & a_i=b_j \\ 1, & a_i\ne b_j \end{cases} $$ 则递推式为： $$ lev_{a,b}(i,j)= \begin{cases} \max(i,j), & \min(i,j)=0 \\ \min\left\{ lev_{a,b}(i-1,j)+1,\; lev_{a,b}(i,j-1)+1,\; lev_{a,b}(i-1,j-1)+\delta(a_i,b_j) \right\}, & \text{otherwise} \end{cases} $$ 三项分别对应： 1. $lev(i-1,j)+1$：删除 $a_i$ 2. $lev(i,j-1)+1$：插入 $b_j$ 3. $lev(i-1,j-1)+\delta(a_i,b_j)$：若相等则不改，代价 0；否则替换，代价 1 #### 伪代码 ```text Function LevenshteinDistance(S1, S2) m = length(S1) n = length(S2) Create DP[m+1][n+1] // 初始化 For i = 0 to m: DP[i][0] = i For j = 0 to n: DP[0][j] = j // 递推 For i = 1 to m: For j = 1 to n: If S1[i-1] == S2[j-1] cost = 0 else cost = 1 DP[i][j] = min( DP[i-1][j] + 1, // 删除 DP[i][j-1] + 1, // 插入 DP[i-1][j-1] + cost // 替换 ) return DP[m][n] ```