202x 秋期末

源 DOCX 的封面写着“2022 年秋季学期”，内页却同时写有“2022—2023 学年第 1 学期”和“2021 年 12 月 14 日”。由于这些日期彼此冲突，本页不猜测真实年份，按约定记为“202x 秋期末”。

原 Word 中的公式并未丢失，而是以 Office 数学对象保存；普通文本提取会漏掉它们。以下题面根据文档中的数学对象恢复，文字和公式均改写为 Markdown/KaTeX，不用整页截图。

一、简答题（20 分）

将下列两组函数按如下方式排序：如果 $f(n)=O(g(n))$ ，则 $f(n)$ 排在 $g(n)$ 前；当且仅当 $f(n)=\Theta(g(n))$ 时，函数 $f(n)$ 和 $g(n)$ 之间写成集合 $\{f(n),g(n)\}$ 。如无特殊说明， $\log n=\log_2 n$ 。

例如，对 $n$ 、 $\sqrt n$ 、 $n+\sqrt n$ ，正确顺序可以写成

\left(\sqrt n,\{n,n+\sqrt n\}\right).

A 组

(\log n)^{2022},\quad n^2\log(n^{2022}),\quad 4n^{3/2},\quad 2.022^n,\quad n\log_4 n.

B 组

2^{2^n},\quad n^3,\quad \binom n{n/2},\quad n!,\quad \binom n3.

提示：可以比较 $\log f(n)$ 与 $\log g(n)$ ，也可以比较 $2^{f(n)}$ 与 $2^{g(n)}$ 。

查看第 1 题答案与解析

A 组的顺序是

(\log n)^{2022} \prec n\log_4n \prec 4n^{3/2} \prec n^2\log(n^{2022}) \prec 2.022^n.

其中换底公式只改变常数， $n\log_4n=\Theta(n\log n)$ ；又因为

\log(n^{2022})=2022\log n,

所以 $n^2\log(n^{2022})=\Theta(n^2\log n)$ 。

B 组中

\binom n3=\frac{n(n-1)(n-2)}6=\Theta(n^3),

而由 Stirling 公式

\binom n{n/2}=\Theta\left(\frac{2^n}{\sqrt n}\right).

因此顺序是

\left\{n^3,\binom n3\right\} \prec \binom n{n/2} \prec n! \prec 2^{2^n}.

二、算法设计题（20 分）

利用函数 Test(x, y)，将 $n$ 个小球放进 $n$ 个不同的筐子，使每个小球都恰好找到合适的筐子。

Test(x, y) 的参数 $x$ 是小球、 $y$ 是筐子，返回“小球太大了”“小球太小了”或“小球正合适”。除这个跨类型比较外，不能直接比较两个小球或两个筐子。

设计一个最坏时间复杂度为 $O(n^2)$ 的算法。
设计一个平均时间复杂度为 $O(n\log n)$ 的算法。

查看第 2 题答案与解析

最坏 $O(n^2)$ 的直接做法：依次取每个尚未匹配的小球，扫描所有尚未匹配的筐子，直到 Test 返回“正合适”。第 $i$ 轮至多比较 $n-i+1$ 次，总比较次数为

n+(n-1)+\cdots+1=\Theta(n^2).

平均 $O(n\log n)$ 的方法类似随机快速排序：

从当前小球集合随机选择一个枢轴球 $x$ 。
用 $x$ 测试所有筐子，把筐子分成“太小”“正合适”“太大”，并找到与 $x$ 匹配的筐子 $y$ 。
再用 $y$ 测试其余小球，把小球作对应划分。
分别递归匹配较小的两组和较大的两组。

每层划分是线性的；随机枢轴使递归树的期望高度为 $O(\log n)$ ，所以期望时间为 $O(n\log n)$ ，最坏情况仍可能达到 $O(n^2)$ 。

三、算法设计题（30 分）

一次出行所需装备由 $n$ 个零件 $E_1,E_2,\ldots,E_n$ 组成。受经济和物流限制，每月只能购买一个零件。若零件 $E_i$ 首月售价为 100 元，之后每推迟一个月，其价格就乘以增长率 $r_i>1$ ：第二个月是 $100r_i$ ，第三个月是 $100r_i^2$ ，依此类推。零件可以按任意顺序购买。

举例说明“增长率最低的零件优先”不一定使总花费最小。
证明“增长率最高的零件优先”总能使总花费最小。
给出按该策略安排购买顺序的算法，并分析时间复杂度。

查看第 3 题答案与解析

只看两个初价相同、增长率分别为 2 和 10 的零件。低增长率优先时总价为

100+100\times10=1100,

高增长率优先时总价为

100+100\times2=300.

因此“最低增长率优先”不是最优策略。

证明最高增长率优先可用相邻交换。设两个相邻购买位置对应指数 $p$ 和 $p+1$ ，且 $r_i>r_j>1$ 。若先买 $i$ ，两件的成本为

100\left(r_i^p+r_j^{p+1}\right);

若先买 $j$ ，成本为

100\left(r_j^p+r_i^{p+1}\right).

函数 $h(r)=r^p(r-1)$ 在 $r>1$ 上严格递增，因此

r_i^p(r_i-1)>r_j^p(r_j-1),

等价于“先买 $i$ ”的成本更低。故任何存在增长率逆序的方案都可通过交换变得更优；不断消除逆序后，得到按 $r_i$ 降序的最优顺序。

算法只需按增长率从大到小排序，时间复杂度 $O(n\log n)$ ；输出顺序需 $O(n)$ 空间，若原地排序则额外空间取决于排序实现。

四、算法设计题（30 分）

在操作系统 Anix 中，一个文件可以看作有序字符串的集合，第 $i$ 个字符串称为第 $i$ 行。允许执行三种操作：

插入一行；
删除一行；
交换相邻两行。

交换较便宜，插入和删除较贵。文件比较功能 diff(A, B) 要通过一系列操作把文件 $A$ 变成文件 $B$ 。设 $A$ 、 $B$ 都恰有 $n$ 行；变换中每一行至多参与一次交换，而且交换的两行在 $A$ 、 $B$ 中都分别相邻。

给出动态规划递推式。
用循环写出基于该递推式的伪代码。
分析时间复杂度。

查看第 4 题答案与解析

设插入、删除、相邻交换的代价分别为 $c_i,c_d,c_s$ 。令 $dp[i][j]$ 表示把 $A$ 的前 $i$ 行变成 $B$ 的前 $j$ 行的最小代价。初值为

dp[i][0]=ic_d,\qquad dp[0][j]=jc_i.

一般位置先考虑删除或插入：

dp[i][j]=\min\left\{ dp[i-1][j]+c_d, dp[i][j-1]+c_i \right\}.

若 $A_i=B_j$ ，还可以不付代价地匹配这两行：

dp[i][j]\leftarrow\min\{dp[i][j],dp[i-1][j-1]\}.

若 $i,j\ge2$ ，且

A_{i-1}=B_j,\qquad A_i=B_{j-1},

则可交换相邻两行：

dp[i][j]\leftarrow \min\{dp[i][j],dp[i-2][j-2]+c_s\}.

for i = 0..n:
    dp[i][0] = i * deleteCost
for j = 0..n:
    dp[0][j] = j * insertCost

for i = 1..n:
    for j = 1..n:
        dp[i][j] = min(
            dp[i - 1][j] + deleteCost,
            dp[i][j - 1] + insertCost
        )
        if A[i] == B[j]:
            dp[i][j] = min(dp[i][j], dp[i - 1][j - 1])
        if i >= 2 and j >= 2
           and A[i - 1] == B[j]
           and A[i] == B[j - 1]:
            dp[i][j] = min(dp[i][j], dp[i - 2][j - 2] + swapCost)

return dp[n][n]

交换转移一次消耗两个相邻位置，因此同一行不会在这条转移链上连续参与两次交换，符合题目限制。共有 $O(n^2)$ 个状态，每个状态只做常数次比较，时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(n^2)$ ；若只求代价，可进一步压缩保存有限行。

一、简答题（20 分）

A 组

B 组

二、算法设计题（20 分）

三、算法设计题（30 分）

四、算法设计题（30 分）

评论