算法设计与分析 2025秋42系期末考试

一、填空

基于比较的排序算法“最坏情况”的时间复杂度下界是__________。
贪心算法具有__________性质。
P问题是指能在__________时间内解决的判定问题。
根据主定理， $T(n) = aT(n/b) + f(n)$ ，当 $f(n) = O(n^{\log_b a - \epsilon})$ 时， $T(n) =$ __________。
$V = O(\sqrt{n}) , E = O(n)$ 时， Edmunds Karp 算法的复杂度为__________。

二、复杂度分析

$T(n) = T(n - 2) + n^2$
$T(n) = T(n / 2) + T(n / 4) + T(n / 8) + n$
$T(n) = 2T(n / 7) + n ^ 3$
$T(n) = T(\sqrt{n}) +\log{n}$
$T(n) = 2T(n / 2) + n\log{n}$

三、简答题

简述 $BFS$ 的原理，并给出一个实际应用的例子。
简述 $0-1$ 背包和分数背包的区别，并说明贪心算法为何适用于分数背包问题但不适用于0-1背包问题。
简述 $P$ 、 $NP$ 、 $NPC$ 问题的定义，并给出证明一个问题是 $NPC$ 问题的一般步骤。

四、流程题（非原题，仅供参考）

根据 $dijkstra$ 算法的求解流程，填空下列表格：

alt text

Steps	0	1	2	3	4	5	6	Selected Node
1	0	$+\infty$	$+\infty$	$+\infty$	$+\infty$	$+\infty$	$+\infty$	0
2
3
4
5
6
7

五、算法设计题

给定一个包含 $n$ 个整数的数组 $r[1...n]$ ，为 $n$ 个同学的得分，下面为每个同学分糖果的规则：
1. 每个同学至少分得一个糖果。
2. 相邻的同学中，得分高的同学必须比得分低的同学分得更多的糖果。
请设计一个算法，计算出最少需要多少个糖果才能满足上述规则。请给出算法思路、伪代码和时间复杂度分析。
给定一个矩阵 $A_{n \times n}$ ，其中每一行从上到下和每一列从左到右都是递增排序的，即 $A_{ij} < A_{i+1,j}$ 且 $A_{ij} < A_{i,j+1}$ ，题目保证任意 $A_{ij}$ 互不相等。题目确保矩阵中存在一个点 $A_{ij}$ ，使得 $A_{ij} = i + j$ ，请给出一个算法快速找到该点。请给出算法思路、伪代码和时间复杂度分析。
给定一个 $n$ 行 $m$ 列的二维网格 $M$ ，其中一部分单元格有障碍物，无法通行。每个单元格只能从上下左右四个方向进入。
1. 给定起点 $S(x_s, y_s)$ 和终点 $T(x_t, y_t)$ ，请设计一个算法，计算从起点到终点的最短路径长度。如果无法到达终点，返回 -1 。请给出算法思路和时间复杂度分析。
2. 给定 $k$ 个点对，求是否有 $k$ 条互不相交的路径连接对应点对，如果有则给出一种可行方案。请设计一个算法解决该问题，并给出算法思路和时间复杂度分析。经验证，该问题为NPC问题，故修改题干如下：给定 $k$ 个起点、 $k$ 个终点 ，求是否有 $k$ 条互不相交的路径连接任意一对起点和终点，且每个起点或终点被使用且仅被使用一次。
给定一个背包容量为 $W$ 的背包和 $n$ 件物品，每件物品有重量 $w_i$ 和价值 $v_i$ 。
1. 计算在不超过背包容量的前提下，能够获得的最大总价值。请给出算法思路和时间复杂度分析。
2. 若相邻物品不能同时选择，计算在不超过背包容量的前提下，能够获得的最大总价值。请给出算法思路和时间复杂度分析。

L.D.J 记忆版 特别鸣谢：zzy、wxj、lqc、wzy、jyf、lmz

参考解析

以下解析根据课程课件和通用算法结论整理，不是课程组公布的标准答案。建议先按原题限时作答，再逐题展开核对。

一、填空题解析

1. 基于比较的排序算法在最坏情况下的时间复杂度下界是__________。

查看第 1 题答案与解析

答案： $\Omega(n\log n)$ 。

决策树有至少 $n!$ 个叶结点，树高至少为

\left\lceil\log_2(n!)\right\rceil=\Omega(n\log n).

归并排序、堆排序能做到 $O(n\log n)$ ，所以上下界合起来是 $\Theta(n\log n)$ 。

**2.** 贪心算法具有__________性质。

查看第 2 题答案与解析

答案：贪心选择性质。一个问题能被贪心正确求解，通常还要具备最优子结构；只写“最优子结构”并不能区分贪心和动态规划。

3. P 问题是指能在__________时间内解决的判定问题。

查看第 3 题答案与解析

答案：确定性多项式时间。

4. 对递推式

T(n)=aT(n/b)+f(n),

当 $f(n)=O\bigl(n^{\log_ba-\varepsilon}\bigr)$ 时， $T(n)=$ __________。

查看第 4 题答案与解析

答案：

T(n)=\Theta\bigl(n^{\log_ba}\bigr).

这是主定理第一种情形：递归子问题的总代价占主导。

5. 当 $V=O(\sqrt n)$ 、 $E=O(n)$ 时，Edmonds-Karp 算法的复杂度为__________。

查看第 5 题答案与解析

Edmonds-Karp 的复杂度是 $O(VE^2)$ ，代入得到

O\bigl(\sqrt n\cdot n^2\bigr)=O(n^{5/2}).

二、复杂度分析解析

1. $T(n)=T(n-2)+n^2$ 。

查看第 1 题答案与解析

每次把规模减少 2，共展开约 $n/2$ 层：

T(n)=T(n-2k)+\sum_{i=0}^{k-1}(n-2i)^2.

取 $k\approx n/2$ ，平方和为 $\Theta(n^3)$ ，故

T(n)=\Theta(n^3).

2. $T(n)=T(n/2)+T(n/4)+T(n/8)+n$ 。

查看第 2 题答案与解析

递归树第一层所有子问题规模之和是

n\left(\frac12+\frac14+\frac18\right)=\frac78n.

以后每层继续乘 $7/8$ ，所以非递归代价形成几何级数：

n+\frac78n+\left(\frac78\right)^2n+\cdots=\Theta(n).

因此 $T(n)=\Theta(n)$ 。

3. $T(n)=2T(n/7)+n^3$ 。

查看第 3 题答案与解析

$a=2$ 、 $b=7$ ，而 $n^{\log_7 2}$ 的次数远小于 $n^3$ 。满足主定理第三种情形，故

T(n)=\Theta(n^3).

4. $T(n)=T(\sqrt n)+\log n$ 。

查看第 4 题答案与解析

第 $i$ 层的非递归代价为

\log\left(n^{1/2^i}\right)=\frac{\log n}{2^i}.

递归深度是 $\Theta(\log\log n)$ ，但各层代价是几何级数：

\log n+\frac12\log n+\frac14\log n+\cdots=\Theta(\log n).

因此 $T(n)=\Theta(\log n)$ 。

5. $T(n)=2T(n/2)+n\log n$ 。

查看第 5 题答案与解析

这里 $n^{\log_2 2}=n$ ，而 $f(n)=\Theta(n\log n)$ ，是主定理的扩展临界情形：

T(n)=\Theta(n\log^2 n).

从递归树看也一样：第 $i$ 层总成本是 $n(\log n-i)$ ，共 $\log n$ 层，求和得到 $\Theta(n\log^2 n)$ 。

三、简答题解析

1. BFS 的原理与应用

查看答案与解析

BFS 从源点开始，用队列按“距离层”扩展：先访问所有距离为 1 的点，再访问距离为 2 的点，以此类推。顶点第一次入队时即被标记，并记录距离和前驱，避免重复搜索。

在无权图中，BFS 首次到达某个顶点时走过的边数最少，因此可以求无权最短路。典型应用还包括网格迷宫最短路、社交网络的最少关系层数、二分图染色等。邻接表实现的复杂度为 $O(V+E)$ 。

2. 0-1 背包与分数背包

查看答案与解析

0-1 背包中每件物品只能完整地取或不取，决策是离散的，通常用动态规划，复杂度 $O(nW)$ 。
分数背包允许只取物品的一部分，可按单位重量价值 $v_i/w_i$ 从高到低贪心，复杂度由排序决定，为 $O(n\log n)$ 。

分数背包中，若方案先拿了较低单位价值的重量，就能用同样重量的更高单位价值物品替换而不变差，因此交换论证成立。0-1 背包不能随意切分物品，这种局部替换可能受剩余容量限制，最高单位价值的物品未必属于全局最优解。

3. P、NP、NPC 与 NPC 证明套路

查看答案与解析

P：能由确定性算法在多项式时间内解决的判定问题。
NP：给定一个候选证书后，能在多项式时间内验证其正确性的判定问题。
NP-hard：所有 NP 问题都能在多项式时间内归约到它的问题。
NPC：既属于 NP，又是 NP-hard 的问题。

证明新问题 $B$ 是 NPC，通常分两步：

证明 $B\in NP$ ：给出证书以及多项式时间验证器。
选择已知 NPC 问题 $A$ ，构造多项式时间归约 $A\le_p B$ 。

归约方向不能写反。要证明 $B$ 至少和 $A$ 一样难，应把 $A$ 的实例变成 $B$ 的实例。

四、Dijkstra 流程题解析

题目给出的参考图如下，要求填写每轮暂定距离与所选结点。

Dijkstra 流程题中的有向带权图

查看完整流程

从结点 0 出发。每轮选择尚未确定且暂定距离最小的结点，再松弛它的出边。

轮次	选中结点	$d(1)$	$d(2)$	$d(3)$	$d(4)$	$d(5)$	$d(6)$
1	0	5	2	$\infty$	$\infty$	$\infty$	$\infty$
2	2	5	2	8	$\infty$	10	$\infty$
3	1	5	2	6	11	10	$\infty$
4	3	5	2	6	7	8	$\infty$
5	4	5	2	6	7	8	14
6	5	5	2	6	7	8	11
7	6	5	2	6	7	8	11

最终最短距离为 $(0,5,2,6,7,8,11)$ 。例如到 6 的最短路是 $0\to1\to3\to5\to6$ ，长度为 $5+1+2+3=11$ 。

五、算法设计题解析

1. 最少糖果

每个同学至少得到一颗糖；相邻同学中，分数更高者必须得到更多糖。求最少糖果总数。

查看算法、伪代码与复杂度

只从左向右扫描只能满足“比左邻居分高”的约束，只从右向左扫描只能满足另一侧。分别计算两种最低要求，再逐点取最大值即可。

left[1..n] = 1
right[1..n] = 1

for i = 2 .. n:
    if r[i] > r[i - 1]:
        left[i] = left[i - 1] + 1

for i = n - 1 .. 1:
    if r[i] > r[i + 1]:
        right[i] = right[i + 1] + 1

answer = sum(max(left[i], right[i]))

$\max(left_i,right_i)$ 同时满足左右两侧的下界，而且任何合法方案都不能低于这两个下界，因此所得方案最小。时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ ；还可复用一个数组把额外空间降到 $O(n)$ 或进一步优化。

2. 在递增矩阵中寻找 $A_{ij}=i+j$

矩阵每行向下、每列向右严格递增，元素互不相同，并保证存在满足 $A_{ij}=i+j$ 的位置。

查看算法、成立条件与复杂度

若题目默认 $A_{ij}$ 是整数，可令

B_{ij}=A_{ij}-i-j.

因为严格递增的整数相邻至少增加 1，所以 $B$ 沿行、列均不减。此时可以像搜索有序矩阵一样从右上角开始：

i = 1, j = n
while i <= n and j >= 1:
    value = A[i][j] - i - j
    if value == 0: return (i, j)
    if value > 0:  j -= 1
    else:          i += 1

每一步删除一行或一列，时间复杂度 $O(n)$ ，空间复杂度 $O(1)$ 。

需要注意：回忆版题干没有明确写“整数矩阵”。若允许任意实数， $A$ 严格递增并不能保证 $A_{ij}-i-j$ 单调，上面的 $O(n)$ 算法不再有证明；此时题面条件不足以推出该快速算法。这是回忆题中应保留的不确定点。

3. 带障碍网格上的路径

3.1 单个起点到终点的最短路

查看算法与复杂度

把每个可通行单元格看作顶点，与上下左右相邻的可通行格连无权边，从 $S$ 做 BFS。第一次到达 $T$ 时的层数就是最短路径长度；若队列清空仍未到达，则返回 $-1$ 。

网格有 $nm$ 个单元格，每格最多检查四条边，所以时间复杂度 $O(nm)$ ，空间复杂度 $O(nm)$ 。

3.2 $k$ 个起点与 $k$ 个终点的互不相交路径

勘误后的题意是：起点和终点可以任意配对，但每个端点恰好使用一次，路径之间不能共享单元格。

查看网络流建模

这是顶点容量为 1 的最大流：

每个可通行格 $v$ 拆成 $v_{in}\to v_{out}$ ，容量为 1，保证一个格子最多被一条路径使用。
对相邻格子 $u,v$ ，连 $u_{out}\to v_{in}$ ，容量为 1。
超级源点向每个起点的 $v_{in}$ 连容量 1 的边。
每个终点的 $v_{out}$ 向超级汇点连容量 1 的边。
若最大流等于 $k$ ，流分解给出 $k$ 条互不相交路径；否则不存在。

拆点后顶点和边仍是 $O(nm)$ 。若用 Dinic，通用最坏界可写成 $O(V^2E)$ ；实际单位容量网格通常远快于这个保守上界。

4. 背包及相邻物品限制

4.1 标准 0-1 背包

查看状态转移

令 $dp[i][c]$ 表示只考虑前 $i$ 件物品、容量为 $c$ 时的最大价值：

dp[i][c]=\max\left(dp[i-1][c],\ dp[i-1][c-w_i]+v_i\right),

第二项仅在 $c\ge w_i$ 时可选。答案为 $dp[n][W]$ ，时间复杂度 $O(nW)$ 。若压缩成一维数组，容量必须从大到小枚举，防止同一物品被重复使用。

4.2 相邻物品不能同时选择

查看状态转移

若不选第 $i$ 件，来自 $dp[i-1][c]$ ；若选第 $i$ 件，则第 $i-1$ 件必须不选，只能从前 $i-2$ 件转移：

dp[i][c]=\max\left(dp[i-1][c],\ dp[i-2][c-w_i]+v_i\right).

边界可设 $dp[0][c]=0$ ，并把 $dp[-1][c]$ 视为 0。时间复杂度 $O(nW)$ ，空间可用滚动数组降到 $O(W)$ 。

算法设计与分析 2025 秋 42 系期末考试

算法设计与分析 2025秋42系期末考试

一、填空

二、复杂度分析

三、简答题

四、流程题（非原题，仅供参考）

五、算法设计题

参考解析

一、填空题解析

二、复杂度分析解析

三、简答题解析

1. BFS 的原理与应用

2. 0-1 背包与分数背包

3. P、NP、NPC 与 NPC 证明套路

四、Dijkstra 流程题解析

五、算法设计题解析

1. 最少糖果

2. 在递增矩阵中寻找 $A_{ij}=i+j$

3. 带障碍网格上的路径

3.1 单个起点到终点的最短路

3.2 $k$ 个起点与 $k$ 个终点的互不相交路径

4. 背包及相邻物品限制

4.1 标准 0-1 背包

4.2 相邻物品不能同时选择

评论

算法设计与分析 2025 秋 42 系期末考试

算法设计与分析 2025秋42系期末考试

一、填空

二、复杂度分析

三、简答题

四、流程题（非原题，仅供参考）

五、算法设计题

参考解析

一、填空题解析

二、复杂度分析解析

三、简答题解析

1. BFS 的原理与应用

2. 0-1 背包与分数背包

3. P、NP、NPC 与 NPC 证明套路

四、Dijkstra 流程题解析

五、算法设计题解析

1. 最少糖果

2. 在递增矩阵中寻找 Aij=i+jA_{ij}=i+jAij​=i+j

3. 带障碍网格上的路径

3.1 单个起点到终点的最短路

3.2 kkk 个起点与 kkk 个终点的互不相交路径

4. 背包及相邻物品限制

4.1 标准 0-1 背包

4.2 相邻物品不能同时选择

评论

2. 在递增矩阵中寻找 $A_{ij}=i+j$

3.2 $k$ 个起点与 $k$ 个终点的互不相交路径