算法与数据结构 · 第 7 课(第一周复习)
从四类证明到一个完整算法:在线维护 + 第 k 小选择
2026 年 10 月 26 日|第 1 周复习日|正文约 16 分钟
本日不引入新专题。把第 1–6 课的“摊还分析、递归树、比较下界、Quickselect/BFPRT、非均匀递归”连接起来,检查何时能说最坏、摊还、期望及下界。
一、学习目标(约 1 分钟)
学完能独立回答:
- 给定一串任意 Push/Pop,如何证明整串更新快,而不错误声称每次更新都快?
- 最终若只需第 k 小,为什么不必先排序?
- 同样有两个递归子问题,为什么归并常为 (\Theta(n\log n)),BFPRT 却为 (O(n))?
- 输入重复、容量很小、随机枢轴不理想时,哪些结论需要改写?
成本模型: 一次 Push/Pop 的基本工作记为 1,扩/缩容时每复制一个存活元素再记 1;比较和移动一个键耗费 (O(1))。操作序列不要求随机。选第 k 小的 k 采用从 1 开始的排名。
二、动机:把“更新”和“查询”当成不同的证明任务(约 2 分钟)
考虑一个在线收集数据的容器,先处理 (m) 次合法的末尾插入/删除,最终剩 (n\ge1) 个元素(允许重复),然后回答“第 (k) 小是多少?”
flowchart TD
A["m 次任意 Push / Pop"] --> B["动态数组:满则扩倍,删除后 ≤ 1/4 则缩半"]
B --> C["最终 n 个键,允许重复"]
C --> D{"只需要第 k 小吗?"}
D -->|是| E["三路分区:L 小于 p、E 等于 p、G 大于 p"]
E --> F{"k 属于哪一段?"}
F -->|L| H["仅递归左侧"]
F -->|E| I["直接返回 p"]
F -->|G| J["仅递归右侧,更新 k"]
D -->|需要全部有序| K["比较排序:通常 Θ(n log n)"]
这段流程里有三个完全不同的问题。
| 需要证明什么 | 本周用到的工具 | 最关键的量词 |
|---|---|---|
| (m) 次更新总成本 | 第 1、5 课:势函数、阈值迟滞 | 任意合法操作序列 |
| 对 (n) 个键求第 (k) 小 | 第 4、6 课:分区不变量、递归规模 | BFPRT 最坏;随机枢轴期望 |
| 为什么不必完整排序 | 第 2、3、6 课:递归树、决策树下界 | 排序需区分 (n!) 种次序,选择不必 |
三、算法设计与数值 Trace(约 4 分钟)
维护 ((n,C)):初始 ((0,1)),容量 (C) 始终是 2 的幂。
Push(x):
if n == C: resize(2*C) # 复制 n 个旧元素
A[n] = x; n += 1
Pop():
require n > 0
n -= 1
if C > 1 and n <= C/4:
resize(C/2) # 复制删除后仍存活的 n 个元素
Select(A, k): # 1 <= k <= |A|
if |A| == 1: return A[0]
p = PivotByMediansOfFive(A)
partition A into L(<p), E(=p), G(>p)
a = |L|; b = |E|
if k <= a: return Select(L, k)
if k <= a+b: return p
return Select(G, k-a-b)
设输入操作为:依次 Push ([8,3,8,1,6,3,9,2]),再 Pop 一次,再 Push (5)。
| 时刻 | 操作 | 更新后 ((n,C)) | 本步复制量 |
|---|---|---|---|
| 0 | 初态 | (0,1) | 0 |
| 1–2 | Push 8、3 | (2,2) | 1 |
| 3–4 | Push 8、1 | (4,4) | 2 |
| 5–8 | Push 6、3、9、2 | (8,8) | 4 |
| 9 | Pop(删 2) | (7,8) | 0 |
| 10 | Push 5 | (8,8) | 0 |
因此十次基本操作记 10,发生复制 (1+2+4) 次。注意最后一次 Push 时 (n=7<C=8),不必扩容。Lv2 将改用另一组操作,让你检验删除触发的缩容成本。
更新后的数据为 ([8,3,8,1,6,3,9,5])。为了直观看出选择不必排序,示例暂取一个候选枢轴 (p=6)(此处只是示范一次分区,并非声称 BFPRT 一定选到 6):
L (<6): [3,1,3,5] a = 4
E (=6): [6] b = 1
G (>6): [8,8,9] c = 3
若查询 k=6:跳过 L 与 E,在 G 中查局部第 1 小。
若下一轮枢轴为 8:等值段覆盖所需排名,立即返回。
分区不变量: 完成扫描后,(L) 所有键严格小于 (p),(E) 全等于 (p),(G) 严格大于 (p);目标排名通过 (k-a-b) 的更新保持不变。分区内部元素无需排序。对于重复键,必须把等值段 (E) 整体识别出来。
四、关键证明一:更新为什么总计 (O(m))?(约 3 分钟)
第 5 课的分段势函数可以同时处理扩容与缩容:
[
\Phi(n,C)=
\begin{cases}
2n-C,&n\ge C/2,
C/2-n,&n<C/2.
\end{cases}
\qquad \Phi\ge0.
]
势函数不是机器真的存储的信用。初态 ((0,1)) 的势能为 (1/2),是常数而不是 0。
定义摊还成本 (\widehat c_i=c_i+\Phi_i-\Phi_{i-1}),按操作分类:
- 不扩容的 Push: 真实成本 1,势能上升至多 2,所以 (\widehat c_i\le3)。
- 发生扩容的 Push: 扩容前 (n=C),扩容后 ((n’,C’)=(C+1,2C))。复制 (C) 项,真实成本 (C+1),势能从 (C) 变成 2,故 (\widehat c_i=3)。
- 不缩容的 Pop: 真实成本 1;势能增量至多 1,所以 (\widehat c_i\le2)。
- 发生缩容的 Pop: 对 (C\ge4),在第一次触及 (C/4) 阈值时,从 (n=C/4+1) 删除到 (n’=C/4),复制 (C/4) 项;旧势能 (C/4-1),新势能 0,故 (\widehat c_i=2)。当 (C=2) 时,删至空并缩到 1,复制 0 项,摊还成本是 (3/2);(C=1) 不缩容。
求和时所有中间势能相消:
[ \sum_{i=1}^m c_i =\sum_{i=1}^m\widehat c_i+\Phi_0-\Phi_m \le 3m+\tfrac12, ]
所以无论怎样合法地交替 Push/Pop,总更新成本都是 (O(m))。但某一次扩容依然可能需要 (\Theta(n)) 次复制,不能宣称“单次最坏 (O(1))”。
反例提醒: 若负载刚到 (1/2) 就缩半,从满表 ((r,r)) 开始反复 Push、Pop,会在 ((r,r)\leftrightarrow(r+1,2r)) 之间抖动,每两次操作复制 (\Theta(r)) 项。引入 (1/4) 缩容阈值是为了避免这个对抗性序列。
五、关键证明二:BFPRT 为什么最坏 (O(n))?(约 3 分钟)
先把 (n) 个键分成若干个五元组,求各组中位数,再递归选出“中位数的中位数”作为 (p)。最多 (\lceil n/5\rceil) 个组中位数需要递归处理。
忽略末尾不完整组及常数级舍入误差:至少一半组中位数不大于 (p),每个这样的完整五元组至少有 3 个元素不大于 (p)。大于等于 (p) 一侧对称成立。于是有不少于 (3n/10-O(1)) 个键落在每一侧的非严格关系内。
三路分区剔除整段 (E) 后,剩余需要递归的单侧最多 (7n/10+O(1)) 项。因此
[ T(n)\le T(\lceil n/5\rceil)+T(7n/10+O(1))+cn. ]
用强归纳试探 (T(t)\le Kt)。递归项之和至多
[ K(0.2n+0.7n)+cn+O(K) =0.9Kn+cn+O(K). ]
取充分大的 (K)(严格大于 (10c)),再选充分大的 (n) 吸收舍入误差、有限小规模并入基例,就得到 (T(n)=O(n))。
现在对照第 2、6 课:
[ \underbrace{2T(n/2)+\Theta(n)}_{\text{每层规模守恒,约 }\log n\text{ 层}} \quad\Longrightarrow\quad \Theta(n\log n), ]
[ \underbrace{T(n/5)+T(7n/10)+\Theta(n)}_{\text{子问题规模总比例 }0.9<1} \quad\Longrightarrow\quad O(n). ]
不要只数递归调用个数。 归并必须处理两个互补区间;BFPRT 的第一支是寻找好枢轴,第二支才是在一侧继续选择。这两个递归工作之和的比例小于 1,是最坏线性上界的关键。
六、边界、空间与证明地图(约 2 分钟)
整个流程在合法 (1\le k\le n) 下:更新 (O(m)),BFPRT 查询最坏 (O(n)),合计 (O(m+n)=O(m)),因为 (n\le m)。动态数组容量始终为 (O(n+1));采用容易理解的数组式三路分区与五元组实现,选择阶段可用 (O(n)) 额外存储;原地实现可以更省空间,但需额外证明索引与交换不变量。
这里并未推翻“比较排序最坏 (\Omega(n\log n))”:排序需要区分互异键的 (n!) 个相对次序,而选择只要求一个次序统计量。随机 Quickselect 在均匀随机选枢轴、正确三路分区条件下期望 (O(n)),但单次随机执行仍可能遭遇平方级最坏情况。若用两路 Lomuto 且比较条件是 (\le p),全相等数组会每次只缩小 1,随机选枢轴也救不了这个特定退化。
本周证明选择器:
| 题目关键词 | 首选证明工具 | 常见错误 |
|---|---|---|
| 任意操作序列总成本 | 势能望远镜、阈值不变量 | 把摊还误当单次最坏 |
| 同规模分治 (aT(n/b)+f(n)) | 逐层工作 / Master | 漏算叶层或正则性 |
| 不等规模分治 | 逐层规模、Akra–Bazzi | 硬套同规模 Master |
| 比较排序下界 | 决策树叶子 (\ge n!) | 误用到选择或整数排序 |
| 只找第 k 小 | 分区不变量、递归大小 | 把两侧都排序或忽视重复键 |
七、四级自测(共 100 分;首次只给题目和中立提示)
建议按 Lv1 → Lv4 作答。前三题有客观评分,Lv4 按证明步骤评分;下列题目不公布答案或解析。
Lv1|机制与保证的量词|15 分|预计 2 分钟|单选
设 m 次合法 Push/Pop 之后剩 n 个键(可能重复),只需要第 k 小。关于复杂度保证,哪一项严格正确?
A. 动态数组每次摊还 O(1),因此每次更新的最坏时间也是 O(1)。
B. 比较排序有 Ω(n log n) 下界,因此任何比较型第 k 小选择算法也有 Ω(n log n) 下界。
C. 采用三路分区的 BFPRT 最坏 O(n);随机 Quickselect 在均匀随机选枢轴时有期望 O(n);二者都不必确定全部键的顺序。
D. 随机 Quickselect 只要随机选枢轴,就能保证对每一次随机结果都在 O(n) 时间结束。
可选提示:分清单次最坏、任意操作序列摊还、随机期望;排序要输出的内容是否比选择更多?
Lv2|更新序列的精确成本|20 分|预计 3 分钟|数值
动态数组初态 (n,C)=(0,1),满时容量翻倍;删除后若 n≤C/4 且 C>1 则容量减半。每次 Push/Pop 基础成本 1,每复制一个存活元素再计 1。依次 Push 4、1、7、2、8;然后连续 Pop 三次;最后 Push 6。求这 9 次更新的真实总成本(不计后续选择算法)。
可选提示:依次记录每次更新后的 (n,C),确认第 3 次 Pop 是否触发缩容;扩容与缩容复制数要分开累计。
Lv3|反例与递归边界|25 分|预计 4 分钟|多选
下列哪些说法成立?(多选,选出全部正确项)
A. 若 T(n)≤T(⌈n/5⌉)+T(7n/10+O(1))+cn 且基例适当,则可通过线性归纳证明 T(n)=O(n)。
B. 对于 T(n)=T(n/3)+T(2n/3)+Θ(n),每层子问题规模之和至多 n,所以总时间必为 Θ(n)。
C. 对 n 个互异键仅找第 k 小,比较决策树仍必须区分全部 n! 种输入次序,因此最坏比较次数必为 Ω(n log n)。
D. 当所有键相同,二路 Lomuto(条件 ≤pivot)即使均匀随机选枢轴也可能每次只缩小 1,导致 Θ(n²);三路分区能在一次扫描后直接终止。
可选提示:检查每层工作与树高的乘积;分清排序的输出信息和选择输出信息;全相等数组下观察枢轴的最终位置。
Lv4|综合算法设计与证明|40 分|预计 9 分钟|开放题
设计一个 BatchSelect 过程:空动态数组先执行任意 m 次合法 Push/Pop(Pop 只删除末尾,键可重复),最终有 n≥1 个元素与合法排名 1≤k≤n,再返回第 k 小。要求:(a) 给出带 1/4 缩容阈值的更新规则、三路分区选择伪代码及维护的不变量;(b) 构造分段非负势函数,证明 m 次更新的真实总成本为 O(m),需处理容量 1、2 边界;(c) 用五元组中位数枢轴证明选择阶段最坏 O(n),并明确为什么递归规模不是 T(n/3)+T(2n/3);(d) 写出整个流程的最坏时间及辅助空间阶,并解释为何不违反比较排序下界、为何随机 Quickselect 的保证不同。
可选提示:先用势能的望远镜求和处理更新;选择时定义 L、E、G 的大小与目标排名的变换;BFPRT 关注两次递归调用的规模比例之和。
八、作答与下一课
回复可用格式:Lv1:字母;Lv2:数值和简要步骤;Lv3:所有选项字母;Lv4:(a)–(d) 的推导。 我会按 15/20/25/40 分逐题批改;总分 80–100 继续原定进度,60–79 追加一题针对性巩固,低于 60 优先复习势函数和递归规模。复习不改变既定课号。
下一课(2026-10-27,第 8 课): 进入第 2 周“随机化 / 概率 / 哈希”,先从 Las Vegas 与 Monte Carlo、随机枢轴的期望保证和随机性假设切入,并与本周选择算法衔接。