算法设计与分析复习笔记

第一部分：算法基础与 RSA 加密

RSA 加密算法

1. 加密过程

• 明文 $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)，使得

等价于存在整数 (k)，满足

👉 这就是一个典型的线性丢番图方程

只要 $\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 的线性组合”

也就是最终要得到：

其中 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}$ 的逆元。

回代法里你做的是：

• 一层一层代
• 每次更新「当前余数 = 前两个余数的线性组合」

表格法只是把：

中的 $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$​

   真正被用到的不是余数，而是“商”。表格法 只吃商，不管余数

2. 填表：

结果： 最后一行的 16 就是逆元。

4. 反复平方算法

反复平方算法的目标：

用 $O (\log n)$ 次运算 代替 $O (n)$ 次连乘

把指数写成二进制，把幂次拆成若干个平方

也就是：

而每个 $a^{2^k}$ 都可以通过“平方前一个”得到。

1️⃣ 指数拆分

2️⃣ 模运算与乘法兼容

👉 所以我们可以：

• 每一步都 先取模
• 数字永远不会变大

算法步骤

Step 1：指数二进制化

把 n 写成二进制。

Step 2：反复平方（预处理）

依次计算：

Step 3：按二进制位相乘

只乘 二进制中为 1 的位 对应的幂。

示例

计算 $14^3 \pmod{55}$

虽然指数小，但流程完全一样。

Step 1：指数二进制化

Step 2：反复平方（每一步都取模）

第 1 项：

第 2 项：

所以：

Step 3：选中二进制为 1 的幂相乘

因为：

所以：

计算：

🎯 最终答案

表格解法

计算

Step 1：指数二进制化

Step 2：表格法

最终结果

5. 时间复杂度

RSA 加密与解密的主要计算为模指数运算，采用快速幂算法，其时间复杂度为 $O(\log n)$ 次模乘运算。

6. RSA 的计算可行性和不可攻破性

可行性

已知 p,q，就能：轻松算φ(n)，用扩展 Euclid 算 d 模指数运算可以用快速幂

RSA 的密钥生成和加解密过程均可通过多项式时间算法完成，尤其是模指数运算可采用反复平方算法，因此在计算上是可行的。

不可攻破性

已知 n，不知道 p,q，无法得到μ(n)，无法求 d

在现有计算能力和已知算法条件下，大整数因子分解问题是计算上不可行的，因此 RSA 具有不可攻破性。

0-1 背包问题

1️⃣ 子问题定义（非常关键）

令 dp[i][j] 表示：
从前 i 个物品中选择，背包容量为 j 时可获得的最大价值。

2️⃣ 边界条件

• dp[0][j] = 0（没有物品）
• dp[i][0] = 0（容量为 0）

例题

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/

最好：折半查找 最坏：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²)。

归并排序

核心思想：分而治之(Divide and Conquer)

1. 将数组一分为二
2. 对左右两部分分别进行归并排序
3. 合并两个有序数组

堆排序

【数据结构合集 - 堆与堆排序(算法过程, 效率分析, 稳定性分析)】 https://www.bilibili.com/video/BV1HYtseiEQ8/

主定理

时间复杂度

蛮力法

分治法

算法基础

一、算法基础（共 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 完全归约链（你可以“画成文字”）】

SAT
 ↓
3-SAT
 ↓
CLIQUE（团问题）
 ↓
VERTEX COVER（顶点覆盖）
 ↓
INDEPENDENT SET（独立集）

【中文名称对应（一定要写）】

一（4）列出常见渐近函数的阶（含中文描述）（5 分）

【标准表（建议直接照写）】

一（5）手写多项式合并函数的大师定理（5 分）

【Master 定理标准版】

设递推式为：

三种情况（一定要分条写）

1. 若 $f(n) = O(n^{\log_b a - \varepsilon})$

2. 若 $f(n) = \Theta(n^{\log_b a})$

3. 若 $f(n) = \Omega(n^{\log_b a + \varepsilon})$

二、算法分析（共 25 分）

二（1）动态规划适用问题的两个特征（5 分）

【标准答案】

1. 最优子结构
   原问题的最优解可以由子问题的最优解构成。
2. 重叠子问题
   在递归求解过程中，不同子问题会重复出现。

二（2）说明贪心法与动态规划的不同（5 分）

【标准对比答案】

【一句话总结（加分）】

贪心算法通过局部最优选择期望得到全局最优解，而动态规划通过系统地求解并保存子问题最优解来保证全局最优。

二（3）Levenshtein 编辑距离定义及公式（5 分）

【定义】

编辑距离是将一个字符串转换为另一个字符串所需的最少编辑操作次数，允许的操作包括插入、删除和替换。

【状态转移方程】

令 dp[i][j] 表示将 X 前 i 个字符变为 Y 前 j 个字符的最小操作数：

二（4）编辑距离 DP 伪代码及复杂度（5 分）

【伪代码（简洁考试版）】

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 方程】

【伪代码（简版）】

for i = 1 to n:
    m[i][i] = 0
for l = 2 to n:
    for i = 1 to n-l+1:
        j = i + l - 1
        m[i][j] = ∞
        for k = i to j-1:
            m[i][j] = min(m[i][j],
                          m[i][k] + m[k+1][j] + p[i-1]*p[k]*p[j])

第二部分：核心概念精要

1. 大 O 记法定义及其极限判别准则

对于给定的复杂度函数 $T(n)$，如果存在两个正数 $C$ 和 $n_0$，以及函数 $\tau(n)$，使得当 $n \ge n_0$ 时有 $T(n) \le C \tau(n)$，则称 $T(n) = O(\tau(n))$。

即 $\lim_{n \to \infty} \frac{T(n)}{\tau(n)} \in [0, +\infty)$ 成立。

2. Karatsuba 乘法算法基本思想、伪代码、复杂度、闭式解，递推式

他采用与高斯复数乘法技巧相同的方法。 将 $x_L y_R + x_R y_L$ 表述为 $(x_L + x_R)(y_L + y_R) - x_L y_L - x_R y_R$。 其中 $x_L y_L, x_R y_R$ 是重复计算，使乘法运算由 4 次降低为 3 次，尽管 add 了 3 次加法算法，但加法运算的复杂度是线性的，整体上降低了复杂度。

伪代码：

• 输入：两个 $n$ 位的正整数 $X$ 和 $Y$
• 输出：$X$ 和 $Y$ 的乘积

1. multiplyK(x, y)
2. $n \leftarrow$ $X$ 和 $Y$ 的位数
3. if n = 1 return x * y
4. $x_L, x_R = X$ 的高 $n/2$ 位和低 $n/2$ 位
5. $y_L, y_R = Y$ 的高 $n/2$ 位和低 $n/2$ 位
6. $P_1 = \text{multiplyK}(x_L, y_L)$
7. $P_2 = \text{multiplyK}(x_R, y_R)$
8. $P_3 = \text{multiplyK}(x_L + x_R, y_L + y_R)$
9. return $P_1 \times 10^n + (P_3 - P_1 - P_2) \times 10^{n/2} + P_2$

复杂度分析：

闭式解： $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)$ 有如下闭式解：

5. Knuth 的算法定义及特性

算法是一组有穷规则的集合，这些规则给出了求解特定类型问题的运算序列。它具有 5 个重要特性，即：

1. 有穷性 (Finiteness)
2. 确定性 (Definiteness)
3. 有效性 (Effectiveness)
4. 输入 (Input)
5. 输出 (Output)

6. Euclid GCD 手算表格

7. 适应于动态规划方法求解的问题的 2 个特征

1. 最优子结构性质 (Optimal Substructure)
2. 子问题重叠性 (Overlapping Subproblems)

8. Levenshtein 编辑距离的定义及公式表达

定义： 两个字符串间的编辑距离是指将一个字符串变换为另一个字符串的基本编辑操作数。这里的编辑操作指的是对单个字符的插入、删除和替换 3 种基本编辑操作。

公式：

（注：公式中若 $a_i \neq b_j$ 则 $\delta=1$，否则 $\delta=0$）

9. 给出 Levenshtein 编辑距离的 DP 算法伪代码、复杂度

复杂度： $O(mn)$

伪代码：

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 方程：

复杂度： $T(n, W) = O(nW)$

0-1 背包问题的动态规划算法的伪代码

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 表格 (部分还原)：

结论： 最优解是物品 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$：

逆元推导过程：

即乘法逆元 $d = 3$。

加密与解密运算： 公钥 $(7, 33)$，私钥 $(3, 33)$

加密： $C = m^e \mod n = 30^7 \mod 33$

即 $C=24$

解密： $m = C^d \mod n = 24^3 \mod 33$ ($a=24, b=3, d=1, n=33$)

即 $m=30$

15. 归并算法基本思想、伪代码

Two Way Merge 基本思想：

1. 顺次比较左右两个子数组中的元素
2. 将比较小者放入临时数组
3. 最后将左或右两个子数组中剩余元素复制到临时数组
4. 将临时数组中的元素复制回原数组

伪代码 (TwoWayMerge)：

• 输入：数组 $a$, $p \sim q$ 和 $q+1 \sim r$ 的元素已排好序的数组
• 输出：$p \sim r$ 的元素已排好的数组 $a$