算法与数据结构 · 第 7 课(第一周复习)

从四类证明到一个完整算法:在线维护 + 第 k 小选择

2026 年 10 月 26 日|第 1 周复习日|正文约 16 分钟

本日不引入新专题。把第 1–6 课的“摊还分析、递归树、比较下界、Quickselect/BFPRT、非均匀递归”连接起来,检查何时能说最坏、摊还、期望及下界。

一、学习目标(约 1 分钟)

学完能独立回答:

  1. 给定一串任意 Push/Pop,如何证明整串更新快,而不错误声称每次更新都快?
  2. 最终若只需第 k 小,为什么不必先排序?
  3. 同样有两个递归子问题,为什么归并常为 (\Theta(n\log n)),BFPRT 却为 (O(n))?
  4. 输入重复、容量很小、随机枢轴不理想时,哪些结论需要改写?

成本模型: 一次 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、随机枢轴的期望保证和随机性假设切入,并与本周选择算法衔接。