算法导论-2023-回忆版

发表于 更新于 分类于 本文字数： 8k 阅读时长 ≈ 7 分钟

算法导论 2023年 的回忆版真题，来源于计算机速通之家 | QQ 群号：468081841。

本文连载于算法导论-2023-回忆版| HeZzz.

🙇‍♂️🙇‍♂️🙇‍♂️时间仓促，有不足之处烦请及时告知。邮箱hez2z@foxmail.com 或者在 速通之家 群里 @9¾。

复杂度

给了两段程序代码，问复杂度。

  • 第一小问是最长公共子序列的代码 $O(n^2)$
  • 第二小问是二分搜索代码 $O(\log n)$

第一小问：最长公共子序列:

参考 OJ 题目：最长公共子序列

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def lcs_length(s1, s2):
    m, n = len(s1), len(s2)
    # 创建二维DP数组
    dp = [[0] * (n + 1) for _ in range(m + 1)]
    
    # 填充DP表
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if s1[i-1] == s2[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    
    return dp[m][n]

复杂度分析： 两层嵌套循环，时间复杂度为 $O(m \times n)$，其中 $m$、$n$ 分别为两个字符串的长度。

第二小问：二分搜索:

1
2
3
4
5
6
7
8
9
10
11
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

复杂度分析： 每次将搜索范围缩小一半，时间复杂度为 $O(\log n)$。

中位数

求一个有 $n$（奇数）个元素数组的中位数，设计一个高效的算法，求出最坏情况下的时间复杂度。

参考 OJ 题目：求第 $k$ 小

算法思路（线性时间选择）：

采用快速选择算法（Quick Select），这是分治算法的一个应用：

  1. 选择一个基准元素
  2. 将数组分为小于基准和大于基准的两部分
  3. 根据基准位置判断中位数在哪一部分，递归处理
  4. 最坏情况时间复杂度：$O(n)$

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
import random

def quick_select(arr, k):
    """
    找出数组中第 k 小的元素（k 从 1 开始）
    """
    if len(arr) == 1:
        return arr[0]
    
    # 随机选择基准
    pivot = random.choice(arr)
    
    # 分区
    left = [x for x in arr if x < pivot]
    mid = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    
    if k <= len(left):
        return quick_select(left, k)
    elif k <= len(left) + len(mid):
        return mid[0]
    else:
        return quick_select(right, k - len(left) - len(mid))

def find_median(arr):
    """
    找出奇数长度数组的中位数
    """
    n = len(arr)
    return quick_select(arr, (n + 1) // 2)

其他方法：

  • 快速排序：最坏情况 $O(n^2)$，平均 $O(n \log n)$
  • 归并排序：$O(n \log n)$
  • 线性时间选择：最坏情况 $O(n)$（最优解）

矩阵连乘

参考 OJ 题目：矩阵连乘规则

题目： 给定 $n$ 个矩阵 ${A_1, A_2, …, A_n}$，每个矩阵的维度已知，求最优的矩阵连乘顺序，使得总的乘法次数最少。

算法思路（动态规划）：

根据动态规划思想，采用自顶向下分析，自底向上求解：

  1. 状态定义： $dp[i][j]$ 表示计算矩阵 $A_i \times A_{i+1} \times … \times A_j$ 的最小乘法次数
  2. 初始状态： $dp[i][i] = 0$（单个矩阵不需要乘法）
  3. 状态转移方程：

$$
dp[i][j] = \min_{i \leq k < j} {dp[i][k] + dp[k+1][j] + p_{i-1} \times p_k \times p_j}
$$
其中 $p$ 是维度数组，$p_{i-1}$ 和 $p_i$ 分别是矩阵 $A_i$ 的行数和列数。

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
def matrix_chain_multiplication(p):
    """
    p: 维度数组，p[i-1]和p[i]是第i个矩阵的行数和列数
    返回最小乘法次数
    """
    n = len(p) - 1  # 矩阵个数
    if n <= 1:
        return 0
    
    # dp[i][j] 表示第i到第j个矩阵的最小乘法次数
    dp = [[float('inf')] * n for _ in range(n)]
    
    # 单个矩阵乘法次数为0
    for i in range(n):
        dp[i][i] = 0
    
    # 按照子链长度递推
    for length in range(2, n + 1):  # 子链长度
        for i in range(n - length + 1):
            j = i + length - 1
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + p[i] * p[k+1] * p[j+1]
                dp[i][j] = min(dp[i][j], cost)
    
    return dp[0][n-1]

# 示例：三个矩阵 A1(30×35), A2(35×15), A3(15×5)
p = [30, 35, 15, 5]
result = matrix_chain_multiplication(p)
print(f"最小乘法次数: {result}")  # 输出: 15750

注意： 动态规划保证得到全局最优解。

图像压缩

题目： 将一个 $n$ 像素的图像分成若干段进行压缩存储，每段有固定的段开销，求使得总存储空间最小的分段方案。

问题建模：

  • 设图像有 $n$ 个像素
  • 将图像分为若干段，每段的存储代价 = 段内像素数 + 段开销
  • 假设每段最多 $256$ 个像素，段开销为 $11$
  • 目标：找到最优分段方案，使总存储空间最小

算法思路（动态规划）：

  1. 状态定义： $dp[i]$ 表示前 $i$ 个像素的最小存储空间
  2. 初始状态： $dp[0] = 0$
  3. 状态转移方程：

$$
dp[i] = \min_{1 \leq j \leq \min(i, 256)} {dp[i-j] + j + 11}
$$
其中 $j$ 表示当前段的像素数，$11$ 是段开销。

算法伪代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
算法 ImageCompression(n)
输入: 像素总数 n
输出: 最小存储空间

1. 初始化 dp[0] = 0
2. for i = 1 to n do
3.     dp[i] = ∞
4.     for j = 1 to min(i, 256) do
5.         cost = dp[i-j] + j + 11  // 前i-j个的最优解 + 当前段代价
6.         dp[i] = min(dp[i], cost)
7.     end for
8. end for
9. return dp[n]

Python 实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def image_compression(n, max_segment=256, overhead=11):
    """
    计算图像压缩的最小存储空间
    n: 像素总数
    max_segment: 每段最大像素数（默认256）
    overhead: 段开销（默认11）
    """
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    
    for i in range(1, n + 1):
        # 尝试不同的段长度
        for j in range(1, min(i, max_segment) + 1):
            cost = dp[i - j] + j + overhead
            dp[i] = min(dp[i], cost)
    
    return dp[n]

# 示例
n = 1000  # 1000个像素
min_space = image_compression(n)
print(f"最小存储空间: {min_space}")

注意： 题目如未明确说明，可按教材假设每段最多 $256$ 个像素，段开销 $11$。

贪心

题目： $n$ 个人排队完成任务，每个人完成任务都有一个时间 $t_i$，求使得 $n$ 个人的平均等待时间最小的顺序，并计算总等待时间。

算法思路（贪心算法）：

根据贪心策略，完成任务时间短者优先：

  1. 贪心选择性质： 时间越短的任务越早完成，可使后续等待的人数减少
  2. 策略： 按照完成时间从小到大排序
  3. 证明： 设有两个人 $i, j$，完成时间分别为 $t_i, t_j$（$t_i < t_j$）
    • 若 $i$ 先完成：总等待时间 = $t_i + (t_i + t_j) = 2t_i + t_j$
    • 若 $j$ 先完成：总等待时间 = $t_j + (t_j + t_i) = t_i + 2t_j$
    • 因为 $t_i < t_j$，所以 $2t_i + t_j < t_i + 2t_j$，故时间短者先完成更优

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
def min_average_waiting_time(times):
    """
    计算最小平均等待时间
    times: 每个人完成任务的时间列表
    返回: (最优顺序, 总等待时间, 平均等待时间)
    """
    n = len(times)
    # 按时间从小到大排序（贪心策略）
    sorted_times = sorted(times)
    
    total_waiting = 0
    current_time = 0
    
    for i, t in enumerate(sorted_times):
        current_time += t  # 当前人完成任务的时刻
        if i < n - 1:  # 最后一个人不需要等待
            total_waiting += current_time
    
    avg_waiting = total_waiting / n
    
    return sorted_times, total_waiting, avg_waiting

# 示例
times = [3, 1, 4, 2, 5]
order, total, avg = min_average_waiting_time(times)
print(f"最优顺序: {order}")           # [1, 2, 3, 4, 5]
print(f"总等待时间: {total}")         # 1 + (1+2) + (1+2+3) + (1+2+3+4) = 20
print(f"平均等待时间: {avg:.2f}")     # 4.00

结论： 完成任务时间短者优先，这是贪心算法的典型应用。

智力大冲浪

小伟报名参加电视台的智力大冲浪节目。本次挑战赛吸引了众多参赛者，主持人为了表彰大家的勇气，先奖励每个参赛者 $m$ 元。先不要太高兴，因为这些钱还不一定都是你的。接下来，主持人宣布了比赛规则：

  1. 首先，比赛时间分为 $n$ 个时段，它又给出了很多小游戏，每个小游戏都必须在规定期限 $t_i$ 前完成（$1 \leq t_i \leq n$）
  2. 如果一个游戏没能在规定期限前完成，则要从奖励费 $m$ 元中扣去一部分钱 $w_i$，$w_i$ 为自然数。不同的游戏扣去的钱数是不一样的
  3. 当然，每个游戏本身都很简单，保证每个参赛者都能在一个时段内完成，而且都必须从整时段开始。主持人只是想考考每个参赛者如何安排组织自己做游戏的顺序

作为参赛者，小伟如何赢取最多的钱？

示例数据：

  • 初始奖金：$10000$
  • 游戏个数：$7$
  • 结束时段：$4, 2, 4, 3, 1, 4, 6$
  • 罚款金额：$70, 60, 50, 40, 30, 20, 10$

算法思路（贪心算法）：

  1. 贪心策略： 按罚款金额从大到小排序，优先完成罚款高的游戏
  2. 调度规则： 对于每个游戏，尽可能安排在其截止期限前的最晚时刻
  3. 时间复杂度： $O(n^2)$ 或使用并查集优化到 $O(n \log n)$

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
def max_reward(initial_money, deadlines, penalties):
    """
    计算最大奖金
    initial_money: 初始奖金
    deadlines: 每个游戏的截止时段列表
    penalties: 每个游戏的罚款列表
    """
    n = len(deadlines)
    # 创建游戏列表 (截止时间, 罚款, 索引)
    games = [(deadlines[i], penalties[i], i) for i in range(n)]
    
    # 按罚款从大到小排序（贪心策略）
    games.sort(key=lambda x: x[1], reverse=True)
    
    # 时间槽，初始都为空
    max_time = max(deadlines)
    time_slots = [False] * (max_time + 1)
    
    total_penalty = 0
    completed = []
    
    # 按罚款从大到小遍历游戏
    for deadline, penalty, idx in games:
        # 尝试在截止期限前找到最晚的空闲时段
        for t in range(deadline, 0, -1):
            if not time_slots[t]:
                time_slots[t] = True
                completed.append((idx, t))
                break
        else:
            # 无法安排，需要支付罚款
            total_penalty += penalty
    
    final_money = initial_money - total_penalty
    return final_money, completed, total_penalty

# 示例
initial = 10000
deadlines = [4, 2, 4, 3, 1, 4, 6]
penalties = [70, 60, 50, 40, 30, 20, 10]

final, completed, penalty = max_reward(initial, deadlines, penalties)
print(f"最终奖金: {final}")
print(f"被罚款: {penalty}")
print(f"完成的游戏安排: {sorted(completed, key=lambda x: x[1])}")

解题步骤：

  1. 按罚款从大到小排序：$70, 60, 50, 40, 30, 20, 10$
  2. 依次安排每个游戏到其截止期限前的最晚空闲时段
  3. 无法安排的游戏计入罚款
  4. 最终奖金 = 初始奖金 - 总罚款

注意： 这是 xjk 老师 PPT 原题，贪心策略的典型应用。

整数方程求解（回溯法）

题目： 求解下列不等式的所有整数解： $4x_1 + 3x_2 + 2x_3 = 12$
其中 $x_1, x_2, x_3$ 为大于等于 $0$ 的整数。

要求：

  1. 确定解空间类型，设计剪枝函数
  2. 用回溯法给出所有动态解空间树
  3. 给出所有的整数解

算法分析（回溯法）：

  1. 解空间类型： 子集树（每个变量可以取多个值）

    • $x_1$ 的可能取值：${0, 1, 2, 3}$（因为 $4 \times 3 = 12$）
    • $x_2$ 的可能取值：${0, 1, 2, 3, 4}$（因为 $3 \times 4 = 12$）
    • $x_3$ 的可能取值：${0, 1, 2, 3, 4, 5, 6}$（因为 $2 \times 6 = 12$）

  2. 剪枝函数：

    • 约束函数（控制左子树）： 如果当前计算结果 $current_sum > 12$，则剪枝
    • 限界函数（控制右子树）： 如果当前计算结果 $current_sum$ + 剩余变量取最大值后的结果 $< 12$，则剪枝

  3. 搜索策略： 深度优先搜索（DFS），第 $i$ 层结点搜索第 $i$ 个变量的值

代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
def solve_equation_backtrack():
    """
    回溯法求解 4x1 + 3x2 + 2x3 = 12 的所有整数解
    """
    solutions = []
    coefficients = [4, 3, 2]
    target = 12
    
    def backtrack(index, current_sum, path):
        # 终止条件
        if index == 3:
            if current_sum == target:
                solutions.append(path.copy())
            return
        
        # 计算当前变量的取值范围
        coef = coefficients[index]
        max_val = (target - current_sum) // coef
        
        # 尝试当前变量的每个可能取值
        for value in range(max_val + 1):
            new_sum = current_sum + coef * value
            
            # 剪枝1：约束函数 - 当前和不能超过目标
            if new_sum > target:
                break
            
            # 剪枝2：限界函数 - 检查剩余部分能否达到目标
            remaining = target - new_sum
            remaining_coefs = coefficients[index + 1:]
            if remaining_coefs:
                min_possible = 0  # 全取0
                max_possible = sum(remaining * (remaining // c) 
                                 for c, remaining in zip(remaining_coefs, [remaining] * len(remaining_coefs)))
                # 简化：检查是否有可能达到目标
                if index == 2:  # 最后一个变量
                    if remaining % 2 != 0:
                        continue
            
            path.append(value)
            backtrack(index + 1, new_sum, path)
            path.pop()
    
    backtrack(0, 0, [])
    return solutions

# 求解
solutions = solve_equation_backtrack()
print(f"共有 {len(solutions)} 个整数解：")
for i, sol in enumerate(solutions, 1):
    x1, x2, x3 = sol
    print(f"解{i}: x1={x1}, x2={x2}, x3={x3}, 验证: 4×{x1}+3×{x2}+2×{x3}={4*x1+3*x2+2*x3}")

所有整数解：

  1. $(x_1, x_2, x_3) = (0, 0, 6)$
  2. $(x_1, x_2, x_3) = (0, 2, 3)$
  3. $(x_1, x_2, x_3) = (0, 4, 0)$
  4. $(x_1, x_2, x_3) = (1, 0, 4)$
  5. $(x_1, x_2, x_3) = (1, 2, 1)$
  6. $(x_1, x_2, x_3) = (2, 0, 2)$
  7. $(x_1, x_2, x_3) = (3, 0, 0)$

解空间树： 共有 $7$ 种整数解，遍历过程中约有 $18$ 个结点（不包括剪枝结点）。

回溯法要点：

  • 解空间组织：子集树或排列树
  • 搜索策略：深度优先搜索（DFS）
  • 剪枝函数：约束函数（控制左子树）+ 限界函数（控制右子树）
  • 适用场景：寻找所有最优解