· 算法设计与分析 / 月考训练 / 区间合并 / 二分查找 / 递推式 / 混合排序
算法设计与分析前四课月考:四道综合题与命题思路
这是一章独立的月考训练与讲评。试卷按 90 分钟、100 分组织;答案部分保留算法、关键轨迹、正确性、复杂度和易错点。
下载月考试卷 PDF · 下载答案与讲评 PDF · 试卷 Markdown · 答案 Markdown
一、合并重叠区间
给定 $n$ 个闭区间 $[l_1,r_1],[l_2,r_2],\ldots,[l_n,r_n]$,其中 $l_i\le r_i$。设计时间复杂度尽可能低的算法,合并所有相交的区间(含端点相接),使输出区间互不相交,并按左端点递增排列。
例如:
\[[[15,18],[1,3],[8,10],[3,6]]\longrightarrow [[1,6],[8,10],[15,18]].\]解答
先按左端点递增、左端点相同按右端点递增排序。扫描时维护结果最后一个区间 $[L,R]$:
sort(intervals, key = (left, right))
ans = []
for [l, r] in intervals:
if ans 为空 或 l > ans[-1].right:
把 [l, r] 加入 ans
else:
ans[-1].right = max(ans[-1].right, r)
return ans
闭区间相交当且仅当 $l\le R$,所以只有 $l>R$ 才开启新区间。排序后:
\[[1,3],[3,6],[8,10],[15,18].\]扫描得到:先放入 $[1,3]$;$[3,6]$ 与其在端点 3 相交,合并为 $[1,6]$;$[8,10]$ 和 $[15,18]$ 分别新开区间。最终为 $[[1,6],[8,10],[15,18]]$。
扫描不变式是:结果中的区间已经合并了此前所有相交连通的输入区间,并按左端点递增排列。若 $l>R$,当前区间不可能与任何更早结果相交;若 $l\le R$,把右端点更新为 $\max(R,r)$ 正好覆盖当前连通分量。排序耗时 $O(n\lg n)$,扫描耗时 $O(n)$,总时间 $O(n\lg n)$;输出之外的辅助空间为 $O(1)$,若计入排序与输出存储则为 $O(n)$。
二、旋转升序数组中的二分查找
给定严格递增数组旋转后的结果 $A$,要求在 $O(\lg n)$ 时间内返回目标 $s$ 的下标;不存在则返回 $-1$。例如 $[0,1,2,4,5,6,7]$ 旋转为 $[4,5,6,7,0,1,2]$。
解答
l = 0, r = n - 1
while l <= r:
m = floor((l + r) / 2)
if A[m] == s: return m
if A[l] <= A[m]:
if A[l] <= s < A[m]: r = m - 1
else: l = m + 1
else:
if A[m] < s <= A[r]: l = m + 1
else: r = m - 1
return -1
对 $A=[4,5,6,7,0,1,2]$ 查找 $s=0$:
| 轮次 | $(l,m,r)$ | 判断 | 保留区间 |
|---|---|---|---|
| 1 | $(0,3,6)$ | 左段有序,$0$ 不在 $[4,7)$ | $[4,6]$ |
| 2 | $(4,5,6)$ | 右段有序,$0<1$ | $[4,4]$ |
| 3 | $(4,4,4)$ | $A[4]=0$ | 返回 4 |
查找 $s=3$ 时第一轮同样保留 $[4,6]$;第二轮右段值域是 $[1,2]$,不含 3,因此保留 $[4,4]$;最后检查 $A[4]=0$,返回 $-1$。
循环不变式是:若目标存在,则它位于当前闭区间 $A[l..r]$。严格递增且只旋转一次,故中点左右至少一侧有序;根据目标是否落在该有序段的值域内,安全丢弃另一侧。每轮区间至少减半,所以时间 $O(\lg n)$,辅助空间 $O(1)$。
三、课件 4-1 递推式
设 $T(n)=\Theta(1)$($n$ 不超过常数时)。令 $p=\log_ba$,比较 $f(n)$ 与 $n^p$。
| 递推式 | 关键比较 | 紧确界 |
|---|---|---|
| $T(n)=2T(n/2)+n^4$ | $p=1$,$n^4$ 主导 | $\Theta(n^4)$ |
| $T(n)=T(7n/10)+n$ | 等比展开 $n+(7/10)n+\cdots$ | $\Theta(n)$ |
| $T(n)=16T(n/4)+n^2$ | $p=2$,同阶 | $\Theta(n^2\lg n)$ |
| $T(n)=7T(n/3)+n^2$ | $p=\log_3 7<2$ | $\Theta(n^2)$ |
| $T(n)=7T(n/2)+n^2$ | $p=\log_2 7>2$ | $\Theta(n^{\log_2 7})$ |
| $T(n)=2T(n/4)+\sqrt n$ | $p=1/2$,同阶 | $\Theta(\sqrt n\lg n)$ |
| $T(n)=T(n-2)+n^2$ | $n^2+(n-2)^2+\cdots$ | $\Theta(n^3)$ |
前三个主定理判断分别是:额外项比基准幂大、等比项递减、额外项与基准同阶。第七题不能直接套主定理,展开后有 $\Theta(n)$ 项,每项总量形成平方和级别,故为 $\Theta(n^3)$。
四、快速排序与插入排序混合算法
随机快速排序递归到子数组长度少于 $k$ 时停止;顶层快排结束后,对整个数组做一次插入排序。假设元素互异、枢轴均匀随机、$2\le k\le n$。
解答
不同终止小块第一次被某个祖先枢轴分开。左块所有元素小于该枢轴,右块所有元素大于该枢轴,因此跨块没有逆序对;剩余逆序对只能在同一小块内部。
插入排序每向右移动一个大于当前 key 的元素,就恰好消除一个逆序对。若第一阶段剩余逆序对数为 $I$,插入阶段时间为 $\Theta(n+I)$。设小块长度为 $m_1,\ldots,m_s$,则 $m_i<k$ 且 $\sum_i m_i\le n$,所以:
故插入阶段为 $O(nk)$。
长度为 $m$ 的一次划分需要 $\Theta(m)$。固定跟踪一个元素,把划分代价平均分给区间元素。枢轴秩位于中间一半时,称为好枢轴;其条件概率至少为 $1/2$,并使元素所在子问题规模至多缩为 $3m/4$。从 $n$ 缩到小于 $k$ 需要 $O(\lg(n/k))$ 次成功缩小;每次成功前坏枢轴的期望等待次数为常数。因此每个元素参与划分的期望次数为 $O(1+\lg(n/k))$,对所有元素求和:
\[\mathbb E[T_{\mathrm{quick}}]=O\left(n+n\lg\frac nk\right).\]加上插入阶段得到:
\[\boxed{\mathbb E[T(n,k)]=O\left(nk+n\lg\frac nk\right)}.\]代入阈值:
| $k$ | 总上界 |
|---|---|
| $2$ | $O(n\lg n)$ |
| $\Theta(\lg n)$ | $O(n\lg n)$ |
| $\Theta(\sqrt n)$ | $O(n^{3/2})$ |
| $n$ | $O(n^2)$ |
固定常数或至多对数阈值保持 $O(n\lg n)$;实践中的最佳整数阈值还受缓存、比较器、递归和常数开销影响,需要针对实现与硬件测量。
命题思路总结
四题分别考查排序后扫描与不变式、局部有序下的二分排除、主定理与展开法、以及把算法结构和逆序对/随机期望合并分析。前两题与 LeetCode 56「Merge Intervals」、LeetCode 33「Search in Rotated Sorted Array」属于同类经典题型;递推式来自课程配套的 CLRS 分治练习,混合排序对应 CLRS 7.4-5。
后续模拟卷沿用五个命题动作:改变一个关键条件;要求算法、轨迹、正确性和复杂度同时作答;加入空输入、相接区间、目标不存在等边界;把期望与最坏、渐近阈值与实践阈值并列;让多道题复用排序、二分、不变式、递推、逆序对和期望这些分析工具。