RedMoon / 训练日志

· 算法设计与分析 / 月考训练 / 区间合并 / 二分查找 / 递推式 / 混合排序

算法设计与分析前四课月考:四道综合题与命题思路

这是一章独立的月考训练与讲评。试卷按 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$,所以:

\[I\le\sum_i\binom{m_i}{2} \le\frac{k-1}{2}\sum_i m_i \le\frac{n(k-1)}2=O(nk).\]

故插入阶段为 $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。

后续模拟卷沿用五个命题动作:改变一个关键条件;要求算法、轨迹、正确性和复杂度同时作答;加入空输入、相接区间、目标不存在等边界;把期望与最坏、渐近阈值与实践阈值并列;让多道题复用排序、二分、不变式、递推、逆序对和期望这些分析工具。