算法设计与分析：期中典型题与模拟试卷

一、期中全真模拟导引与规范答题范式

本篇全面覆盖算法设计与分析课程前四章的代表性题型，包括渐近复杂度计算、分治算法设计、六大经典动态规划实验题、贪心算法交换论证，并附带一套标准的 100 分期中模拟试题。

算法设计规范六步法（评分标准对齐）：

1. 数学建模与问题形式化： 清晰定义符号、输入输出映射与优化目标函数；
2. 状态/循环不变量严密定义： 明确每个状态维度的物理含义与边界；
3. 算法核心逻辑与伪代码： 写出关键转移方程、贪心选择决策或划分策略；
4. 算法正确性证明： 运用数学归纳法、循环不变量或交换论证法（Exchange Argument）展开严密证明，杜绝“显而易见”；
5. 计算复杂度与存储空间分析： 明确给出时间复杂度紧确界 $\Theta$ 与辅助空间复杂度；
6. 边界条件与特判： 针对空输入、全负数、单元素、极值等边界情况进行处理说明。

二、渐近复杂度与基础概念分析

典型题 1-1：多项式与指数的渐近阶数判定

题意：求 $3n^2+10n$、$n^2/10+2^n$、$21+1/n$ 的渐近阶。

推理：

• 第一项 $3n^2+10n$：由最高次多项式项主导，为 $\Theta(n^2)$；
• 第二项 $n^2/10+2^n$：指数项增长速率在极限下远超任意固定次多项式，为 $\Theta(2^n)$；
• 第三项 $21+1/n$：在 $n \ge 1$ 时取值始终介于 21 与 22 之间，为 $\Theta(1)$。

易错辨析：渐近表达式说明的是函数的极限增长阶，而非精确代数消去。若仅写 $O$，给出的是上界；要求精确增长阶时应尽量给出紧确界 $\Theta$。

典型题 1-2：$O(1)$ 与 $O(2)$ 的渐近等价性辨析

渐近函数集合完全相同，因为常数 2 可被渐近定义中的正实数常数系数吸收。两次具体操作在物理指令执行上确实可能比一次慢，但在渐近分析中均属于不随输入规模 $n$ 变化的常数增长阶，因此二者属于同一等价类。

典型题 1-4：计算能力提升对不同复杂度问题规模的影响

设旧机器在时间预算内可处理规模为 $n$ 的输入，新规模为 $N$，满足方程 $T(N) \le 64 \cdot T(n)$：

由此可明确：对于指数阶算法，即使算力发生巨大提升，输入规模也仅能获得微小的加法增长，必须依靠算法设计优化到多项式时间。

三、递归分治经典题型精解

典型题 2-1：多重集众数与重数问题

题意：给定多重集 $S$，求出现次数最多的元素（众数）及其重数。例如 $S = \{1, 2, 2, 2, 3, 5\}$，输出众数 2，重数 3。

方法设计：
先执行归并排序（耗时 $O(n\log n)$），随后自左向右线性扫描一次（耗时 $O(n)$）。相同元素在排序后必定物理连续，最大的连续段长度即为众数的重数。

std::pair<int, int> mode(std::vector<int> a) {
    if (a.empty()) return {-1, 0};
    std::sort(a.begin(), a.end());
    int answer = a[0], best = 0;
    for (int i = 0; i < static_cast<int>(a.size()); ) {
        int j = i + 1;
        while (j < static_cast<int>(a.size()) && a[j] == a[i]) ++j;
        if (j - i > best) {
            best = j - i;
            answer = a[i];
        }
        i = j;
    }
    return {answer, best};
}

时间复杂度 $O(n\log n)$，辅助空间 $O(n)$。需注意：众数（Mode）不等于多数元素（Majority Element）。多数元素要求重数严格大于 $n/2$，而众数仅要求重数在所有候选者中最大。

典型题 2-3：半数集多重集计数与记忆化优化

题意：从自然数 $n$ 开始，可在其左侧添加一个不大于最近添加数一半的正整数，并递归继续；按多重集计数。例如 $\operatorname{set}(6) = \{6, 16, 26, 126, 36, 136\}$，共 6 个。

递推推导：
设 $F(n)$ 为半数集的大小。

• 不添加任何数字的数 $n$ 自身贡献 1；
• 若首个添加的数字为 $i$，则满足 $1 \le i \le \lfloor n/2 \rfloor$，后续所有合法前缀数共有 $F(i)$ 种。

逐项手算：$F(1)=1$，$F(2)=F(3)=2$，$F(4)=F(5)=4$，$F(6)=1+1+2+2=6$。
引入前缀和数组 $P(t) = \sum_{i=1}^t F(i)$，则 $F(n) = 1 + P(\lfloor n/2 \rfloor)$，自底向上递推可在 $O(n)$ 时间和 $O(n)$ 空间内完成求解。

典型题 2-5：含重复元素的全排列生成

题意：输出给定元素集合的所有不同排列，并统计总数量。例如 aacc，输出 6 种不重复排列。

回溯与去重机制：
在递归树的每个位置上，仅针对互不相同的字符分别开设分支；递归前消耗该字符的剩余计数，回溯时恢复。若使用标准库：

std::sort(s.begin(), s.end());
long long count = 0;
do {
    std::cout << s << '\n';
    ++count;
} while (std::next_permutation(s.begin(), s.end()));

不同排列总数为多项式系数 $P = n! / \prod_c f_c!$。输出所有排列的时间下界为 $\Omega(nP)$。

四、动态规划经典题与六大实验题精解

典型题 3-1：双机独立任务最优调度

题意：每个作业只能交给机器 A 或机器 B，在两机上所需时间分别为 $a_i, b_i$。求完成全部作业所需的最短时间（两机完工时刻的较大者达到极小）。例如 $a=(2,5,7,10,5,2)$，$b=(3,8,4,11,3,4)$。

状态定义与转移：
定义 $D_i[t]$ 为：前 $i$ 个作业分配完毕、机器 A 累计耗时恰为 $t$ 时，机器 B 所需的最小时间。

• 分配给 A：从 $D_{i-1}[t]$ 转移至 $D_i[t + a_i]$，B 负载不变；
• 分配给 B：从 $D_{i-1}[t]$ 转移至 $D_i[t]$，B 负载增加为 $D_{i-1}[t] + b_i$。

最终全局答案为 $\min_t \max(t, D_n[t])$。设 $S = \sum_i a_i$，算法时间复杂度为 $O(nS)$，空间滚动后为 $O(S)$，属于伪多项式时间算法。

典型题 3-3：环形石子合并与区间动态规划

题意：环形排布的石子堆，每次合并相邻两堆，新增堆大小为本次得分，求合并为一堆的最小与最大总得分。例如 $(4,4,5,9)$，最小得分 43，最大得分 54。

破环成链与区间 DP：
将数组复制一倍拼接成长度为 $2n$ 的线性链。定义 $L[i][j]$ 与 $H[i][j]$ 为合并连续区间 $[i, j]$ 的最小与最大得分。前缀和为 $W(i, j)$：

按区间长度 $r = 2 \to n$ 递增填表。最终扫描全部合法的长度为 $n$ 的区间 $[i, i+n-1]$（$1 \le i \le n$），取对应极值。时间复杂度为 $O(n^3)$，空间复杂度为 $O(n^2)$。

典型题 3-4：数字三角形自底向上动态规划

题意：从数塔顶端走到最后一层，每次只能走向相邻下一层的两个位置，求沿途数字和的最大值。

自底向上转移：
最后一层状态初始化为节点原本数值，向上递推：

答案为 $dp[1][1]$。自底向上递推天然规避了边界越界特判，时间复杂度 $\Theta(n^2)$，原地更新空间仅需 $O(n)$。

典型题 3-6：租用游艇最短路径动态规划

题意：从起点 1 号码头到达终点 $n$ 号码头，已知任意两码头间的直达租金 $r(i, j)$，求最小总花费。

转移方程：
定义 $dp[i]$ 为到达码头 $i$ 的最小费用（$dp[1] = 0$）：

时间复杂度 $\Theta(n^2)$，空间复杂度 $O(n)$。

典型题 3-8：序列最小 m 段和动态规划

题意：将包含 $n$ 个整数的序列恰好划分为 $m$ 个非空连续段，使得各段元素和的最大值达到极小。输入包含负数。

状态定义与推导：
前缀和记为 $P$。定义 $F[g][i]$ 为前 $i$ 个数恰好划分为 $g$ 段时的最小最大段和。枚举最后一段的起点 $j+1$：

• 初始化：$F[0][0] = -\infty$，其余 $F[0][i] = +\infty$（负无穷用于保证第一段的真实数值被正常保留，防止全负数时被 0 抬高）；
• 复杂度：时间 $O(mn^2)$，滚动优化后空间 $O(n)$。

典型题 3-13：数字串最大 k 乘积动态规划

题意：在给定的 $n$ 位数字串中插入 $k-1$ 个乘号（切分为 $k$ 个片段），求各片段数值相乘的最大积。

预处理子串数值 $V(l, r)$。定义 $F[g][i]$ 为前 $i$ 位切分为 $g$ 个乘积段时的最大乘积：

初始化 $F[0][0] = 1$，不可达状态记为 $-1$。时间复杂度 $O(kn^2)$，空间复杂度 $O(n^2 + kn)$。

五、贪心算法典型题与交换论证推导

典型题 4-1：会场安排与最小会场数分配

题意：安排所有给定的活动，要求使用的会场总数最少。例如活动 $(1,23), (12,28), (25,35), (27,80), (36,50)$，输出 3。

贪心策略与小根堆维护：
按开始时间升序排列，使用小根堆维护各个会场当前的空闲时间（最后活动的结束时间）。若当前活动开始时间不早于堆顶，则复用该会场并更新其结束时间；否则新开辟会场。时间复杂度 $O(n\log n)$。

典型题 4-2：序列最优合并与哈夫曼树模型

题意：合并长度分别为 $a, b$ 的两个序列，比较次数为 $a+b-1$。给定序列长度 $5, 12, 11, 2$，求最大与最小总比较次数。输出 78 52（最大在前）。

• 最小比较次数：小根堆贪心合并最小两项（Huffman 模型）：
  $(2+5)\to 7\text{ (6次)},\quad (7+11)\to 18\text{ (17次)},\quad (18+12)\to 30\text{ (29次)}.$
  总比较次数为 $6 + 17 + 29 = 52$；
• 最大比较次数：大根堆贪心合并最大两项：
  $(12+11)\to 23\text{ (22次)},\quad (23+5)\to 28\text{ (27次)},\quad (28+2)\to 30\text{ (29次)}.$
  总比较次数为 $22 + 27 + 29 = 78$。

典型题 4-5：磁带程序最优存储问题

题意：磁带长度为 $L=50$，程序长度分别为 $2, 3, 13, 8, 80, 20$。求能存下的最多程序个数。

贪心证明：按长度升序排列（$2, 3, 8, 13, 20, 80$）。前 5 个总长为 $2+3+8+13+20 = 46 \le 50$，存 6 个总长达 126 越界，故答案为 5。由交换论证法，任意 $k$ 个程序的总长度不可能低于升序排列前 $k$ 个程序的和。

典型题 4-6：单窗口最优服务次序与平均等待时间

题意：所有顾客同时到达，服务耗时分别为 $56, 12, 1, 99, 1000, 234, 33, 55, 99, 812$。求使平均等待时间最小的服务次序。

推导：按服务时间升序排列（短作业优先 SJF）。
若相邻两人服务耗时满足 $t_{\pi(k)} > t_{\pi(k+1)}$，交换其服务次序后，仅有第 $k$ 位被服务顾客的等待时间减少，总等待时间净减少 $t_{\pi(k)} - t_{\pi(k+1)} > 0$。通过消除所有逆序对可严格证明升序排列使总等待时间达到极小。

六、期中全真模拟试卷（自拟 100 分标准卷）

A. 简答论述题（5 题，每题 6 分，共 30 分）

1. 渐近符号与最坏情况：符号 $O$ 是否必然代表最坏情况？若某算法的平均时间复杂度为 $\Theta(n\log n)$，能否推断出其最坏情况时间复杂度同样为 $\Theta(n\log n)$？
2. 归并排序开销分析：简述归并排序时间复杂度为 $\Theta(n\log n)$ 的推导过程，并说明其辅助空间复杂度来源。
3. 动态规划与贪心对比：动态规划与贪心算法均要求满足“最优子结构性质”，二者的根本区别何在？应用贪心策略时还必须额外证明何种性质？
4. 0-1 背包空间压缩：说明 0-1 背包在压缩至一维数组后，容量循环必须逆序进行的数学依据。若题目要求“背包恰好装满”，数组应如何初始化？
5. Dijkstra 与最小生成树的边权限制：Dijkstra 算法与最小生成树（MST）算法的优化目标有何不同？它们对于图中存在负权边的容忍度是否相同？

B. 算法设计与分析题（3 题，共 70 分）

B1. 利用分治法统计逆序对（20 分）

给定整数数组 $a[0 \dots n-1]$，若 $i < j$ 且 $a[i] > a[j]$，则称 $(a[i], a[j])$ 为一个逆序对。

1. 设计一个时间复杂度为 $O(n\log n)$ 的分治算法；
2. 说明数组 [3, 1, 2, 1] 的计算过程，给出重复元素的处理规则；
3. 给出算法正确性证明与时空复杂度分析。

long long countInversions(std::vector<int>& a) {
    std::vector<int> buffer(a.size());
    auto solve = [&](auto&& self, int l, int r) -> long long {
        if (r - l <= 1) return 0;
        int mid = l + (r - l) / 2;
        long long count = self(self, l, mid) + self(self, mid, r);
        int i = l, j = mid, k = l;
        while (i < mid && j < r) {
            if (a[i] <= a[j]) buffer[k++] = a[i++];
            else { count += (mid - i); buffer[k++] = a[j++]; }
        }
        while (i < mid) buffer[k++] = a[i++];
        while (j < r)   buffer[k++] = a[j++];
        for (int p = l; p < r; ++p) a[p] = buffer[p];
        return count;
    };
    return solve(solve, 0, static_cast<int>(a.size()));
}

B2. 矩阵连乘积动态规划与括号重建（25 分）

设有四个矩阵 $\langle A_1, A_2, A_3, A_4 \rangle$，其维度向量为 $P = (5, 10, 3, 12, 5)$（即 $A_1: 5\times 10$，$A_2: 10\times 3$，$A_3: 3\times 12$，$A_4: 12\times 5$）。

1. 建立动态规划状态转移方程与边界条件；
2. 列出各区间长度下的状态值，给出最小标量乘法次数；
3. 给出最优加括号结构，并说明如何通过辅助数组重构最优方案。

B3. 最小生成树 Kruskal 算法与并查集连通性（25 分）

无向连通带权图顶点为 $\{A, B, C, D\}$，边集为 $\{ (A,B):1,\ (A,C):4,\ (B,C):2,\ (B,D):5,\ (C,D):3 \}$。

1. 采用 Kruskal 算法给出选边演练过程与最终生成树总权重；
2. 解释并查集在该算法中的核心作用与实现逻辑；
3. 说明算法的正确性依据与时间复杂度。若原图不连通，算法如何有效检测？