算法与数据结构 · 第 8 课

随机化算法入门:为什么随机 Quickselect 期望线性,却仍可能最坏平方?

2026 年 10 月 27 日|第 2 周 · 第 1 节|正文约 16–17 分钟(自测另计)

上一课证明了 BFPRT 的最坏线性时间。今天不再重复五元组证明,而是回答另一个问题:不精心挑枢轴,仅靠每轮随机挑一个元素,为什么仍能有可证明的效率?“期望”又究竟保证了什么?

一、学习目标与成本模型(约 1 分钟)

本课结束应能:区分 Las Vegas 与 Monte Carlo;准确指出随机性来自哪里;写出能处理重复值的三路 Quickselect;利用条件概率 + 几何等待证明期望运行时间 (O(n)),并构造其最坏 (\Theta(n^2)) 执行。

明确假设: 输入数组 (A) 和排名 (1\le k\le n) 固定;每轮在当前未处理区间的元素位置上重新均匀抽样,新抽样不受以往枢轴选择偏置;比较、交换和取一个随机索引的成本按 (O(1)) 计;每轮原地三路分区扫描 (O(m)) 项,其中 (m) 为当前区间长度。元素可相等,排名采用升序、从 1 开始的多重集合排名。

二、随机性到底影响“正确性”还是“运行时间”?(约 2 分钟)

Las Vegas 算法: 对每个合法输入,只要算法结束,答案总是正确;随机性影响运行时间或搜索路径。随机 Quickselect 是典型例子:枢轴可能很坏,但正确分区后从未丢掉目标排名。

Monte Carlo 算法: 在受控的计算预算内给出答案,允许经过明确概率界约束的错误。一个直观例子是“快速判断两个等长位数组是否一致”:独立均匀抽取 (t) 个位置逐一比较,只要发现不同就报告“不一致”,否则报告“看上去一致”。若两数组至少有 (\varepsilon n) 个位置不同,则错误地报告一致的概率为

[ \Pr(\text{漏检})\le (1-\varepsilon)^t. ]

为什么?一次抽样未碰到差异的概率至多 (1-\varepsilon),在独立、有放回抽样下,连续 (t) 次未碰到的概率是其 (t) 次方。这里能在少量抽样下保证低误差,依赖“差异比例至少 (\varepsilon)”的前提;若仅差一个位置,错误概率变为 ((1-1/n)^t),不能宣称小样本就很可靠。这是 Monte Carlo 的“错误概率—成本”权衡。

两类算法不能仅根据“有没有 random()”判断:应分别检查输出能否错误、计算成本在哪个随机意义下有界。

三、固定输入与随机运行:期望对谁取?(约 2 分钟)

对一个固定的最坏排列 (A) 及固定 (k),算法可能沿多条由随机数决定的执行轨迹运行。记随机选择序列为 (R),时间为 (T(A,k;R))。我们要证明的是:

[ \boxed{\forall A,\forall k:\quad \mathbb E_R[T(A,k;R)]\le Cn.} ]

这不是“把所有可能输入平均一下”的 average-case 保证。即使输入是对抗性地预先固定的,也对该输入单独成立。

简单回顾离散期望:若随机变量 (X) 取值 (x_i) 的概率为 (p_i),则 (\mathbb E[X]=\sum_i p_ix_i);若观察到了先前抽样的历史 (H),就应使用条件概率 (\Pr(\cdot\mid H)) 与条件期望。今天的证明必须在任意已有历史下仍能推进,而不能只分析第一轮的平均划分。

四、算法:三路分区,永远不丢目标排名(约 3 分钟)

与上课的 BFPRT 相比,只有一处实质变化:从确定性五元组枢轴改为从当前区间均匀随机抽取;小于、等于、大于三路分区及排名更新不变。

RandomQuickselect(A, k):                 # 1 ≤ k ≤ |A|
    lo = 0; hi = |A| - 1                  # k 是当前区间的 1-based 排名
    while lo < hi:
        p = A[RandomIntInclusive(lo, hi)]
        lt = lo; i = lo; gt = hi
        while i <= gt:
            if A[i] < p:
                swap(A[lt], A[i]); lt += 1; i += 1
            elif A[i] > p:
                swap(A[i], A[gt]); gt -= 1
            else:
                i += 1
        a = lt - lo                       # 小于 p 的数量
        b = gt - lt + 1                   # 等于 p 的数量
        if k <= a:
            hi = lt - 1
        elif k <= a + b:
            return p
        else:
            lo = gt + 1
            k -= a + b
    return A[lo]

扫描中不变量(这里只说当前区间):

[ \underbrace{A[lo:lt]}{<p}\quad \underbrace{A[lt:i]}{=p}\quad \underbrace{A[i:gt+1]}{\text{未检查}}\quad \underbrace{A[gt+1:hi+1]}{>p}. ]

特别注意:遇到 (A[i]>p) 时,将它与右端未检查元素交换,不能立刻把 (i) 加一;新换回来的元素尚未分类。每一步都会缩小“未检查”区间,扫描必终止。

分区结束时,原区间里最小的 (a) 个值在 (L),紧接着 (b) 个值都等于 (p),剩下在 (G)。若 (k\le a) 就进入 (L);若 (a<k\le a+b) 直接返回 (p);否则进入 (G),新排名 (k’=k-a-b)。归纳可知目标排名始终被保留,因此随机枢轴不会造成答案错误。每轮至少剔除包含枢轴的非空等值段;迭代实现最终停止。

flowchart TD
    A["固定输入 A、排名 k"] --> B["从当前区间均匀随机抽一个枢轴 p"]
    B --> C["单次扫描:L 小于 p / E 等于 p / G 大于 p"]
    C --> D{"k 落在哪里?"}
    D -->|L| E["只保留 L;k 不变"]
    D -->|E| F["返回 p:正确性不依赖枢轴质量"]
    D -->|G| G["只保留 G;k ← k - |L| - |E|"]
    E --> B
    G --> B

一次数值 Trace。 输入 (A=[7,2,9,1,4,8,3,6]),求第 (5) 小。假设第一次随机选 (p=4):

分组 元素(组内尚未排序) 数量
(L) [2,1,3] 3
(E) [4] 1
(G) [7,9,8,6] 4

因为 (k=5>3+1),进入 (G),新的 (k’=1)。再假设抽到 (p=7),其小于段为 [6],目标落在左段。最后单元素返回 6。这里的 4 和 7 是一条示例随机轨迹,不是“算法必然选择”的枢轴。

五、先算一轮:平均缩小,不等于每轮都缩得好(约 2 分钟)

假设当前有 (m) 个互异键,目标第 (k) 小;把枢轴在升序中的名次记为 (j)。由于枢轴从所有位置均匀抽取,(\Pr(j=s)=1/m)。一次分区后需要递归的元素数 (S_j) 是

[ S_j= \begin{cases} m-j, & j<k \quad (\text{进右侧}),
0, & j=k \quad (\text{直接找到}),
j-1, & j>k \quad (\text{进左侧}). \end{cases} \qquad \mathbb E[S]=\frac1m\sum_{j=1}^{m}S_j. ]

这是单轮期望,尚不是整个算法的时间复杂度。更不能随意写 (\mathbb E[T(S)]=T(\mathbb E[S])):对非线性的 (T),把期望移入函数通常不成立。我们需要真正控制可能连续出现的坏枢轴。

六、关键证明:坏枢轴会发生,为什么总期望还是 (O(n))?(约 3 分钟)

给当前 (m) 个元素排一个带唯一位置标签的全序(相等键可用固定标签打破名次平局;算法本身仍按键值三路分区)。定义“好枢轴”为其排名 (j) 落在

[ \boxed{\lfloor m/4\rfloor+1\ \le j\ \le\ \lceil3m/4\rceil}. ]

这个集合里至少有 (m/2) 个排名,因为

[ \lceil3m/4\rceil-\lfloor m/4\rfloor\ge m/2. ]

故在任意已发生的历史下,下一轮选到好枢轴的条件概率至少 (1/2)。若选到好枢轴,左侧至多 (j-1\le3m/4) 个,右侧至多 (m-j\le3m/4) 个;等值元素一并从递归中剔除,只会让剩余规模更小。

现在不要求连续每轮都好,而是把算法切成若干阶段:每个阶段从当前规模 (M) 开始,直到选到一次好枢轴或算法提前结束。

若 (N) 是本阶段发生的分区次数,由于每轮的条件成功概率 (\ge1/2),

[ \Pr(N>t)\le(1/2)^t, \quad \mathbb E[N] =\sum_{t=0}^{\infty}\Pr(N>t) \le \sum_{t=0}^{\infty}2^{-t}=2. ]

所以阶段里虽然可能遇到很多坏枢轴,但期望至多扫描两轮。坏轮不会使区间变大,每轮至多耗费 (cM),故该阶段的期望成本不超过 (2cM)。

每经历一次好枢轴,下一阶段起始规模最多变为此前的 (3/4)。于是各阶段期望工作量受控于

[ \begin{aligned} \mathbb E[T(n)] &\le 2cn+2c(3n/4)+2c(3/4)^2n+\cdots+O(1)
&\le 2cn\sum_{r\ge0}(3/4)^r+O(1) =\boxed{8cn+O(1)=O(n)}. \end{aligned} ]

这是一个针对任意固定输入的期望上界,只用到每轮条件均匀随机抽样与线性分区成本;证明没有假设每轮缩小 (3/4),也没有用错误的“期望规模代替随机规模”。

七、边界、反例与与 BFPRT 的区别(约 2 分钟)

为什么还有 (\Theta(n^2)) 最坏执行? 对互异键 (1,2,\ldots,n) 查第 (n) 小(最大值),设随机过程每轮恰好都抽中当前最小值。每轮只丢弃一个元素,扫描成本按区间规模依次为 (n,n-1,\ldots,2),总和 (\Theta(n^2))。这条随机轨迹概率虽很小(均匀独立抽样下为 (1/n!)),却是合法轨迹。期望线性不等于每次运行线性。

为什么重复值一定要处理? 若采用“(\le p)”的二路 Lomuto 分区,全相等输入可能每次都只去掉一个元素,随机选什么位置都无法改善。三路分区将整个等值段一次排除,全相等输入一次扫描即可返回。

算法 输出正确性 时间保证 代价与边界
随机 Quickselect + 三路分区 一定正确(Las Vegas) 期望 (O(n)),最坏 (\Theta(n^2)) 枢轴每轮条件均匀抽样;迭代原地辅助空间 (O(1))
BFPRT + 三路分区 一定正确(确定性) 最坏 (O(n)) 需要额外的分组与中位数选择工作
固定预算随机抽样判断“是否一致” 可能漏检(Monte Carlo) 样本数给定时 (O(t)) 误差受差异比例 (\varepsilon) 与独立抽样前提控制

适用前提辨析: 若随机种子对攻击者完全可预测,他可以针对产生的枢轴序列构造坏输入;不能把“对真实随机选择取期望”的数学结论升级成“固定任何种子也具有最坏线性保证”。同时,概率上的快也不等于一定快;重视硬实时最坏延迟时,BFPRT 一类确定性保证可能更合适。

八、今日总结与下一课

本课真正需要记住的不是“随机快”,而是三个逻辑层次:分区不变量保证答案正确;好枢轴的条件概率保证不会在同一尺度上平均停留太久;阶段成本形成收敛几何级数,得到期望线性。 哪一层缺失,都不能直接宣称 Las Vegas 期望 (O(n))。

下一课(2026-10-28,第 9 课): 从选择算法的随机枢轴转向随机哈希:随机函数族、碰撞概率、链地址法为何能在明确负载条件下达到期望 (O(1)),以及为什么不能简单假设“哈希值天然均匀”。

九、四级自测(100 分;首次不给答案)

四题依次考机制辨析、期望数值计算、复杂度边界推理和完整证明。前三题由互动测验客观判分;Lv4 需要书面推导,由自评/人工/ChatGPT 批改。首次不显示答案,提示不泄露选项。

Lv1|Las Vegas / Monte Carlo 与复杂度保证|15 分|预计 2 分钟|单选

关于 Las Vegas、Monte Carlo 和随机 Quickselect,下列哪一项同时正确?

A. Las Vegas 必须在预设时间内返回,允许小概率错误;Monte Carlo 保证答案正确但运行时间随机。

B. 随机 Quickselect 的答案始终正确;每轮在当前区间均匀随机选枢轴时,期望耗时为 O(n),但某次执行仍可能需要 Θ(n²)。

C. 随机 Quickselect 期望线性,因此固定任意一个伪随机种子也能保证最坏 O(n)。

D. 给任何确定性算法加入随机选择,都能自动把最坏运行时间降到 O(n)。

中立提示:区分输出是否允许出错、时间的随机性,以及“期望”到底对什么取平均。

Lv2|枢轴位置的离散均匀分布与期望|20 分|预计 3 分钟|数值

有 n=8 个互异键,目标是第 k=5 小。第一次分区从 8 个当前位置等概率选枢轴,采用三路分区。令 S 为第一次分区后仍需继续处理的子问题元素数;若枢轴恰好第 5 小,则 S=0。求 E[S](单位:元素;填数值)。

中立提示:用枢轴在升序中的名次 j=1,…,8 枚举;分别讨论 j<k、j=k、j>k,再把八种剩余规模平均。

Lv3|条件期望、重复键、递归误区|25 分|预计 4 分钟|多选

下列判断哪些正确?(多选,选出全部正确项)

A. 对任意固定输入(允许重复键)和合法 k,若每轮在当前区间重新均匀抽枢轴并正确三路分区,随机 Quickselect 的期望时间为 O(n)。

B. 随机枢轴自动排除了最坏 Θ(n²) 的执行,因此不需要考虑连续抽到端点的情况。

C. 只要知道 E[S]≤3n/4 且 T 单调,就必然有 E[T(S)]=T(E[S]),可直接替换递归规模。

D. 如果每次条件概率至少 1/2 将规模降到当前规模的 3/4 以下,且每轮工作 O(当前规模),则可用几何等待与分阶段求和证明期望 O(n)。

中立提示:检查“对随机运行时间取期望”与“每次运行的最坏情况”;并回忆一般的非线性函数能否把期望移入函数。

Lv4|算法设计、不变量与概率分析|40 分|预计 9 分钟|开放推导

设计可处理重复键的原地随机 Quickselect(输入长度 n≥1,排名 k 从1开始)。(a) 写出随机枢轴与三路分区伪代码,说明循环不变量和排名更新为何正确(12分);(b) 对当前大小 m,证明“好枢轴”的条件概率至少1/2,且发生时下一子问题大小不超过3m/4,注明整数端点、重复值的处理(10分);(c) 用几何等待和阶段成本严格推出期望 O(n),不得直接假定 E[T(S)]=T(E[S])(12分);(d) 构造一次 Θ(n²) 的合法随机执行,解释为何它不否定期望线性,并与 BFPRT、Monte Carlo 的保证作比较(6分)。

中立提示:可用 [⌊m/4⌋+1, ⌈3m/4⌉] 作为好枢轴名次集合;在两次好枢轴之间,当前区间大小不会增加。

十、作答方式

回复 Lv1:选项;Lv2:数值及简要算式;Lv3:全部选项;Lv4:(a)–(d) 分步证明。批改总分 100 分:80–100 继续,60–79 补一道针对题,低于 60 先复习分区不变量和条件概率;补练不改变自然日课号。