北航算法分析与设计 2024 年秋季期末考试题

北航研究生课程，李东禹、杜皓华老师班级，一共 6 题，每道题 20 分，卷面一共 120 分，拿 100 分即可满分。

其中一、二、四题的答案来自老师给的作业答案。如有错误或补充欢迎在评论区指出。

一、算法设计题

题目：在分析插入排序时，一个重要的临界值是 \(M=\sum_{j=1}^n d_j\)，即输入中“反转”的个数（\(d_j\) 是 \(A[i]\) 左侧且大于它的元素个数）。请给出一个最坏情况下时间复杂度为 \(O(n\log n)\) 的算法，从输入中计算 \(M\)。

答案

由于 \(M\) 的本质是计算原始输入数列中当 \(i<j\) 时 \(A[i]>A[j]\) 的个数，因此考虑改写归并排序实现。

首先，定义“归并反转”为：进行 Merge 操作，即复制 \(A[p..q]\) 到 \(L\)、\(A[q+1..r]\) 到 \(R\) 后，\(x\in L\)、\(y \in R\) 同时 \(x>y\)。

由于在归并排序中，数组元素改变位置的唯一方式是在 Merge 过程中，同时由于合并会使 \(L\) 中的元素保持相同的相对顺序，相应地 \(R\) 中的元素也保持相同的相对顺序，因此两个元素改变其相对顺序的唯一方式就是较大的元素出现在 \(L\) 中，较小的元素出现在 \(R\) 中，因此，每一次“反转”都意味着一次“归并反转”，即它们为一一对应关系。假设我们有一个涉及值 \(x\) 和 \(y\) 的归并反转，其中 \(x\) 原本是 \(A[i]\)，\(y\) 原本是 \(A[j]\)。由于 \(x\) 位于 \(L\) 中，而 \(y\) 位于 \(R\) 中，\(x\) 必须位于包含 \(y\) 的子数组之前的子数组中。因此，\(x\) 一开始位于 \(y\) 的原始位置 \(j\) 之前的位置 \(i\)，所以 \((i, j)\) 是一个反转。

所以，设计基于归并排序的反转计数算法如下：

让 \(z\) 成为 \(L\) 中大于 \(y\) 的最小值。在合并过程中的某个时刻，\(z\) 和 \(y\) 将成为 \(L\) 和 \(R\) 中“暴露”的值，也就是说 \(z = L[i]\) 和 \(y=R[j]\)。此时，将出现包含 \(y\) 和 \(L[i],L[i+1], L[i+2], \dots, L[N_1]\) 的归并反转，而这 \(n_1-i+1\) 归并反转将是唯一涉及 \(y\) 的归并反转。

因此，我们仅需要检测 \(z\) 和 \(y\) 在合并过程中的首次暴露，并将此时的 \(n_1-i+1\) 加入归并反转的总次数中。 \[\begin{aligned} & \mathrm{MERGE}(A, p, q, r) \\ & \begin{aligned} 1 & \quad n_1=q-p+1 \\ 2 & \quad n_2=r-q \\ 3 & \quad 初始化数组\ L[1..n_1+1]\ 和\ R[1..n_2+1] \\ 4 & \quad \mathbf{for}\ i=1\ \mathbf{to}\ n_1 \\ 5 & \quad \quad L[i] = A[p+i-1] \\ 6 & \quad \mathbf{for}\ j=1\ \mathbf{to}\ n_2 \\ 7 & \quad \quad R[j]=A[q+j] \\ 8 & \quad L[n_1 + 1] = \infty \\ 9 & \quad R[n_2 + 1] = \infty \\ 10 & \quad i = 1 \\ 11 & \quad j = 1 \\ 12 & \quad c = 0 \\ 13 & \quad \mathbf{for}\ k=p\ \mathbf{to}\ r \\ 14 & \quad \quad \mathbf{if}\ L[i]\leq R[j] \\ 15 & \quad \quad \quad A[k]=L[i] \\ 16 & \quad \quad \quad i = i + 1 \\ 17 & \quad \quad \mathbf{else} \\ 18 & \quad \quad \quad A[k]=R[j] \\ 19 & \quad \quad \quad j = j+1 \\ 20 & \quad \quad \quad c = c + n_1 - i + 1 \\ 21 & \quad \mathbf{return}\ c \end{aligned} \\\\ & \mathrm{MERGE\text{-}SORT}(A, p, r) \\ & \begin{aligned} 1 & \quad c = 0 \\ 2 & \quad \mathbf{if}\ p<r \\ 3 & \quad \quad q = \lfloor (p + q) / 2 \rfloor \\ 4 & \quad \quad c = c + \mathrm{MERGE\text{-}SORT}(A, p, q) \\ 5 & \quad \quad c = c + \mathrm{MERGE\text{-}SORT}(A, q + 1, r) \\ 6 & \quad \quad c = c + \mathrm{MERGE}(A, p, q, r) \\ 7 & \quad \mathbf{return}\ c \end{aligned}\end{aligned}\]

二、算法设计题

题目：\(n\) 个小球和 \(n\) 个筐子，每个小球正好适合一个筐子。比较这些小球和筐子是否适配的唯一方法是：

\(\mathrm{Test}(x, y)\): \(x\) 是小球，\(y\) 是筐子；返回“小球太大”、“小球太小”或“小球完全合适”。

1. 设计并分析匹配小球和筐子的 \(O(n^2)\)算法
2. 为同一问题设计 \(O(n\log n)\) 算法

答案

1. 写一个双层 for 循环嵌套的函数，内外层循环分别为 \(n\) 个螺栓和螺母，利用 Test 函数对每一个螺栓和筐子都进行比较。因为共要比较 \(n\times n\) 次，所以时间复杂度为 \(O(n^2)\)
2. 假设筐子标有数字 \(1, 2, \dots, n\)，小球也是如此。这数字是任意的，与其大小不对应，而只是用于指代算法描述中的筐子和小球。此外，输出该算法将由 \(n\) 个不同的对 \((i,j)\) 组成，其中筐子 \(i\) 和小球 \(j\) 匹配。算法 MATCH 将代表筐子和待匹配小球：\(N \subset 1,2,\dots ,n\)，代表筐子，\(B ⊆ 1,2,\dots ,n\)，代表小球。

\[\begin{aligned} & \mathrm{MATCH}(N,B) \\ & \begin{aligned} 1 & \quad \mathbf{if}\ |N| == 0 \\ 2 & \quad \quad \mathbf{return} \\ 3 & \quad \mathbf{if}\ |N| == 1 \\ 4 & \quad \quad \mathrm{let}\ N=n\ \mathbf{and}\ B=b\ 输出\ (n, b) \\ 5 & \quad \quad \mathbf{return} \\ 6 & \quad 从\ N\ 随机选取一个筐子\ n \\ 7 & \quad 将\ n\ 与\ B\ 中的每一个小球\ b\ 比较 \\ 8 & \quad B_< = B\ 中比\ n\ 小的所有筐子的集合 \\ 9 & \quad B_> = B\ 中比\ n\ 大的所有筐子的集合 \\ 10 & \quad b = 与\ n\ 匹配的筐子 \\ 11 & \quad 将\ b\ 与\ N-n\ 中的所有筐子比较 \\ 12 & \quad N_<= N\ 中比\ b\ 小的所有小球的集合 \\ 13 & \quad N_>= N\ 中比\ b\ 大的所有小球的集合 \\ 14 & \quad 输出\ (n, b) \\ 15 & \quad \mathrm{MATCH}(N_<, B_<) \\ 16 & \quad \mathrm{MATCH}(N_>, B_>) \end{aligned}\end{aligned}\]

三、算法设计题

问题：你正在为一次出行购买一件具有 \(n\) 个零件 \((E_1, E_2, \dots, E_n)\) 的装备，然而经济和物流原因使得你每月只能购买其中一个零件，所有零件初始价格一样，但你每推迟购买某零件 1 个月，这个零件的售价将以大于 1 的速度增加，即：若零件 \(E_i\) 在首月购买需花费 \(100\) 元，则在第二个月购买需花费 \(100\times r_i\) 元，第三个月为 \(100 \times r_i^2\)，以此类推。你可以按任意顺序购买这些零件。

1. 请举例说明贪心策略“优先购买具有最低的增长率 \(r\) 的零件”无法使用最小花费买到全部零件。
2. 证明贪心策略“优先购买具有最高的增长率 \(r\) 的零件”总是可以使用最小花费买到全部零件。
3. 给出基于贪心策略“优先购买具有最高的增长率 \(r\) 的零件”的零件购买顺序安排算法，并分析其时间复杂度。

四、算法设计题

问题：在一个 \(n \times m\) 的棋盘的格子上放置了不同价值的硬币。假设左上角的单元格为 \((1, 1)\)，右下角的单元格为 \((n, m)\)；单元格 \((i, j)\) 中的硬币价值为 \(c_{ij}\)。机器人从单元格 \((0,0)\) 开始，在棋盘上只能向右或向下移动。

1. 给出一个动态规划算法，用递归方式实现，以确定机器人在棋盘上游荡时应走的路径，从而使收集到的硬币总价值最大化。分析所需时间。
2. 给出用循环方法实现的动态规划算法。分析所需时间。

答案：

1. 从 \((i, j)\) 开始，机器人只能移动到 \((i, j+1)\) 或 \((i+1, j)\)。在移动之后，机器人会面临一个棋盘略小的子问题，起点分别是 \((i, j+1)\) 或 \((i+1, j)\)。这表明问题和子问题之间存在递归关系。如果我们认为 \(C(i, j)\) 是机器人从 \((i, j)\) 出发到 \((n, m)\) 时所能收集到的最大值，那么我们就可以构造出下面的递推关系：

\[C(i, j) = \begin{cases}\max\{C(i, j+1), C(i + 1, j)\} + c_{ij}, &1\leq i<n\ \mathrm{and}\ 1\leq j < m\\C(i, j+1) + c_{ij}, & i = n \\C(i+1, j) + c_{ij}, & j = m \\c_{ij}, & i=n\ \mathrm{and}\ j=m\end{cases}\]

基于递归方式实现的时间复杂度基本上等同于“暴力搜索”我们需要探索所有不同的路径，找出其中的最优路径。也就是说，时间复杂度将与机器人可能走过的路径数量成正比。现在，这变成了一个计数问题：机器人将做 \(n+m-2\) 次运动，其中 \(n-1\) 次是向下运动，\(m-1\) 次是向右运动。这意味着将有\({n+m-2 \choose n-1}\)（或 \({n+m-2\choose m-1}\) 两者相等）不同的路径可供选择。所以，时间复杂度将为 \(\Theta\left({n+m-2 \choose n-1}\right)\)。

2. 使用循环方式进行实现时，我们可以首先构建一个 \(n\times m\) 的表来存储子问题的结果。然后，为了迭代解决问题，我们可以从单元格 \((n, m)\) 开始查表，并反向利用上述递归方法，通过迭代表中与已迭代单元格相邻的单元格来查表。迭代任何单元格都需要 \(O(1)\) 次，因此这种迭代算法的最终复杂度将与表格中的单元格数成正比，即 \(\Theta(nm)\)。

五、算法分析题

问题：考虑以下寻找生成树的“笨”算法：按任意顺序检索图的边，当且仅当一条边与已添加的边不构成循环时将它添加到部分生成树中。

1. 证明这种算法不能在任何有限范围内逼近最小生成树。即，给定一个图和一个边的排序，此算法给出生成树的权重至少是最小生成树权重的 \(k\) 倍 \((\forall k > 0)\)。
2. 假设边的权重都是范围 1~2 之间的实数，给出此“笨”算法的近似边界。

六、算法设计题

问题：我们给定了 \(n\) 份工作 \(J_1, J_2, \dots, J_n\)，其中一些任务互不兼容必须安排在不同的日期，给定一个 \(n\times n\) 的布尔矩阵 \(C\) 有： \[ c_{ij}=\begin{cases} 1 & 如果\ J_i\ 和\ J_j\ 不能安排在同一天\\ 0 & 其他 \end{cases} \]

1. 把这个问题改写成一个决策问题，并证明它是 NP-Complete 的。
2. 设计一个启发式算法找出安排 \(n\) 项工作所需的最少天数。