动机
选择算法要找的是某一个秩的元素,而不是把所有元素完全排好序。围绕主元进行划分后,就能判断目标秩落在哪一侧,因此只需继续处理这一侧。如果每次选出的主元恰好都是剩余元素中最小的,而目标是最大的,那么剩余列表每次只缩短一个元素,总工作量是二次的。若每次均匀随机地选取主元,分析就不同了:平衡的主元出现得足够频繁,使得对每个固定输入,期望总工作量都是线性的。
这个结果是对算法随机选择取期望的代价保证,而不是常数意义下的最坏情形运行时间。在下面的比较模型中,算法总能返回正确秩的元素;随机性只影响工作量的大小。
定义
定义 1.11.1
(选择问题与成本模型)
输入由 个互不相同的全序元素和一个合法的秩 组成。对于大小为 的当前列表,在其元素中均匀地选取一个主元,所用的随机选择在给定当前列表的条件下是全新的。把其余元素划分为比主元小的和比主元大的两部分。若主元在当前列表中的秩等于 ,则返回该主元。否则,在唯一包含目标的一侧继续处理,并在丢弃较小元素和主元时相应调整目标的秩。
假设一次划分(包括选取主元)的代价至多为 个单位,其中 为固定常数;处理只含一个元素的列表的代价至多为 。在这个模型中,我们统计比较次数或其他单位操作。若主元在大小为 的列表中的秩介于 与 之间(含两端),则称该主元是平衡的。
定理
定理 1.11.2
(正确性与终止性)
对于任意的主元选择序列,随机快速选择都会终止并返回所要求的元素。
定理 1.11.3
(期望线性工作量)
对于由 个互不相同元素组成的每个固定输入以及每个合法的目标秩,在算法随机选择上取期望的工作量至多为 的常数倍。
证明思路或证明
证明
(正确性与期望线性工作量)
划分之后,主元的秩等于比它小的元素个数加一。若目标秩等于该值,则主元即为所求。否则,目标位于相应的严格划分部分中,减去被丢弃的较小元素个数以及主元本身,即得它在该部分中的秩。这一不变量对每一种主元选择都成立。递归继续处理的列表比其父列表的元素更少,因此过程会终止,而且单元素的基本情形是正确的。
对于大小为 的列表,平衡秩的个数为
因此,均匀选取的主元以至少 的条件概率是平衡的。若主元平衡,则两个严格划分部分的大小都至多为 :较小一侧至多有 个元素,较大一侧至多有 个元素。
把操作分成若干阶段。一个阶段从当前大小 开始,在第一个平衡主元出现时或算法终止时结束。由于大小只会减小,该阶段内每次操作处理的元素都不超过 个。在还需要再进行一次操作的条件下,主元平衡的概率至少为 。因此,一个阶段持续至少 次操作的概率至多为 ,其期望操作次数至多为 。于是它的期望工作量至多为 。
一个阶段完成后,下一阶段的起始大小至多是前一阶段起始大小的四分之三。因此,无论后面的阶段是否全部出现,它们的起始大小都以 为上界。把它们的期望工作量相加,得到至多
基本情形至多再贡献一个常数 。这就证明了期望线性界。尽管所到达的列表依赖于先前的随机选择,条件概率的论证仍然有效。
证明透视
为什么可以对各阶段求和
每个阶段的起始大小都不超过某个确定的几何级数上界。在给定其全部先前历史的条件下,每个新的主元至少有二分之一的概率结束该阶段。于是,由期望的线性性即可对各阶段的代价求和,而无需假设各阶段的大小相互独立。
例题详解
例题 1.11.4
(秩的更新)
设九个互不相同的元素被划分为四个较小元素、主元 和四个较大元素。主元的秩为五。要找秩为七的元素,就在较大的部分中递归地寻找秩为 的元素。主元不必就是答案,它所做的划分同样是有用的。
例题 1.11.5
(平衡秩)
对于大小为八的列表,平衡秩从 到 ,八种可能中有五种。只要选中其中任何一个,每个严格划分部分至多有六个元素。一般的证明只需要较弱的概率界 以及上界 。
例题 1.11.6
(一个倒霉的序列)
在大小为 的列表上,设目标是最大元素,而每次选中的主元都是当前的最小元素。划分后的大小依次为 ,因此工作量可以是二次的。这个主元序列出现的概率为正,尽管该概率可能很小。
常见错误
反例模式
期望线性并不意味着每次运行都是线性的
上述每次选最小元素为主元的序列是一次合法的执行,其工作量可以是二次的。线性的结论是对固定输入在主元随机性上取平均的工作量,而不是对每次执行都成立的上界。
常见错误
(要求主元必须是中位数)
平衡的主元不必是真正的中位数。它只需要使两个可能保留下来的一侧的大小都以一个常数比例为界;秩在 至 之间已经足够。
常见错误
(把整个执行过程中主元的秩当作相互独立)
阶段论证依赖于在每一个当前列表上都成立的条件概率界;它并不假设整个执行过程中所有主元的秩是相互独立的随机变量。所到达的列表依赖于先前的选择,但无论到达哪个列表,界 都成立。
常见错误
(忘记从秩中扣除较小的元素)
若主元有 个较小元素,而目标的秩满足 ,新的秩是 ,而不是 。对九个元素、主元秩为五、 的情形,目标是四个较大元素中第二小的一个。在这四个元素中寻找秩 是没有意义的。
反例模式
确定性的主元规则没有期望线性的保证
有人会认为取列表第一项作主元与随机主元同样好。取已排序的列表 ,目标秩为 ,并永远以第一项为主元。主元 的秩为一,因此保留列表 ,目标秩为 ,如此类推。各次划分的规模为 ,共做 次比较,而且每次运行都是如此,不只是运气不好时才发生。线性界需要的是均匀的条件主元分布,而不是任意一条规则。
追踪目标的秩
正确性不变量针对的是目标元素,而不是主元是否能很好地估计其秩。设当前目标的秩为 ,而主元有 个比它小的元素。若 ,则在这些较小元素中寻找的恰好是同一个秩。若 ,则主元就是答案。若 ,则被丢弃的 个元素全都排在目标之前,所以目标在较大部分中的新秩为 。元素互不相同保证了每个元素恰好属于三个区域之一,并且主元的秩是唯一的。
划分会重新排列输入列表,但对于保留下来的任何一侧,其内部并不要求有序。若对整个这一侧排序,就会增加本分析没有计入的工作量。算法在较小的列表上重复同样的秩计算,直到找到目标。相比之下,排序算法通常需要处理两侧;这一差别说明了为什么它的递推式可以有不同的增长速率。
例题 1.11.7
(四种可能的主元)
对于已排序的值 ,设目标是秩为二的元素。若主元为 ,则答案立即得到。主元为 时,保留 ,目标秩为一。主元为 时,保留 ,目标秩为二。主元为 时,保留 ,目标秩为二。这四个分支都是正确的;它们后续的代价可以不同。按照平衡的定义,对于大小为四的列表,秩一到三是平衡的。
使阶段论证精确化
以任意一个在大小 处开始一个阶段的历史为条件。若算法在 个不平衡主元之后仍在运行,则其当前大小至多为 。要使该阶段需要第 次操作,先前的每个主元都必须不平衡,并且没有返回答案。在每一步,无论当前列表和目标秩如何,出现不平衡主元的条件概率至多为二分之一。把这些条件概率的上界相乘,得到概率至多为 。这是一条条件概率链;它并不断言当前列表的大小是相互独立的。
对于取非负整数值的随机变量 ,把 写成事件 的示性变量之和,即得尾和恒等式 。把它应用于阶段长度,可得期望的划分操作至多为两次。每次的代价至多为 ,因此以该阶段起始历史为条件,期望阶段代价至多为 。算法可能在出现平衡主元之前就结束;这只会使阶段变短。
对阶段起始大小的几何界在每一次执行中都是确定的。若某个阶段以平衡主元结束且存在新的阶段,则下一个列表不大于该主元所在列表的四分之三,而后者本身又不大于前一阶段的起始列表。因此第 个阶段的起始大小至多为 。对于从未出现的阶段,视其代价为零。条件期望和确定性的大小界给出了上面的几何级数求和,尽管阶段的个数是随机的。
期望代价与尾部陈述
期望并不直接说明每次运行的工作量都不超过 的某个小倍数。马尔可夫(Markov)不等式确实给出了一个基本的尾部界。若总工作量 满足 且 ,则 。例如,至多十分之一的运行其工作量至少为 。这个界是有效的,但可能比较松;更强的尾部陈述需要另行证明。
正确性与运行时间在这里涉及不同的量词。每个合法的主元序列都会返回正确答案,因为每一步都保持秩不变量并且严格缩短列表。期望时间定理对每个固定输入都成立,但它是对算法的随机选择取平均。它不需要假设输入的各种排列是等可能的。在随机主元被抽取之前就固定输入的对手,无法使均匀主元的条件计算失效。
当前主元必须均匀选取这一要求是实质性的。对已排序的列表只选第一个元素是确定性的做法,可能反复选中最小的元素。只随机选取一次下标,之后在划分后沿用某个确定性规则,未必能在后续每个列表上给出均匀的主元。证明要求在每次调用时都具有所述的条件分布;具体实现必须论证其随机化确实提供了这一点。
代价模型与边界情形
在比较模型中,可以把在 中精确均匀地抽取一个整数视为基本操作。如果实现中只有公平的随机比特,则可以抽取足够多的比特来覆盖一个二的幂次范围,并拒绝落在所需范围之外的值。这种拒绝法的期望抽取次数是有限的,但要给出细致的比特代价界,就必须统计抽取次数及其长度。定理中关于选取主元与划分合计代价至多为 的假设,把这一模型选择明确地写了出来。
大小为一的列表是基本情形。此时无需选取主元,直接返回该元素。对于合法的非空列表,主元本身总是被丢弃或被返回,因此每一次递归继续的列表都严格更小。证明排除了不合法的秩以及空输入;具体实现在对列表取下标之前应检查这些前提条件。
当存在相等的键时,必须谨慎地规定二路划分。一种常见的改法是形成小于、等于和大于三个区域,当所需的秩落在等于区域内时返回该键。其正确性和时间分析需要对重复键与随机主元选取给出相应的处理。这里的定理采用互不相同的元素,使得与主元相等就恰好确定一个元素,从而简单的秩证明可以直接适用。
保证的比较
中位数的中位数选择法通过花费工作量来选出具有可证明秩范围的主元,从而给出确定性的最坏情形线性比较次数界。随机快速选择则通过对主元抽样,并证明平衡阶段平均而言很快出现,从而得到期望线性界。尽管两者都避免了对整个输入排序,但它们对某一次倒霉的执行所作的断言是不同的。
在实践中,主元选择、内存移动、递归深度和比较代价都会影响性能。该定理在一个简单的模型下孤立地考察了操作次数。它的价值恰恰在于其假设是明确可见的:条件均匀的主元、互不相同的键、线性的划分代价以及合法的秩。借用这个界之前,应当把另一种实现与这些假设逐一对照。
总结
划分保持目标的秩不变并缩短当前列表。均匀随机的主元有常数的概率丢弃常数比例的元素,所以每个阶段的期望工作量与该阶段的起始大小成线性关系。在出现平衡主元之后,起始大小按几何级数缩小,从而得到期望线性的总工作量。
练习
快速检查
(若一个主元有四个比它小的元素,它的秩是多少?)
解答 · 答案
它的秩为五。
快速检查
(对于大小为八的列表,按定义列出所有平衡秩。)
解答 · 答案
它们是 。
快速检查
(为什么一次正确的执行仍然可能有二次的工作量?)
解答 · 答案
一个倒霉的序列可能使每次划分后保留的列表只缩短一个元素,从而得到二次的划分代价之和。
快速检查
(期望界是对随机输入分布取的平均吗?)
解答 · 答案
不是。输入是固定的;期望是对算法的主元选择取的。