动机
选出第 小的元素并不需要对全部元素排序。围绕主元进行划分后,我们就知道所求的秩位于哪一侧,因此只需在这一侧继续查找。不幸的主元仍会使普通的快速选择(quickselect)耗费二次时间。中位数的中位数方法额外花费一些工作来选取主元,使得每一次足够大的递归调用都能丢弃输入中固定比例的元素。
我们在比较模型中,对互异元素证明最坏情况上界。证明中的常数是有意取得宽松的;关键在于两个递归子问题的规模之和比原规模小一个线性量。
定义
定义 1.10.1
(秩选择与下中位数)
输入是 个互异的全序元素组成的列表,以及秩 ,其中 。秩为 的元素是列表中恰有 个比它小的元素的那一个。 个互异元素的下中位数,是其中秩为 的元素。
当 时,直接对列表排序并返回第 个元素。当 较大时,将列表分成每组五个元素的若干组,最后一组可能不足五个。对每组排序并保留其下中位数。然后递归地选出这 个组中位数的下中位数 。
将原列表划分为小于 的元素、主元 ,以及大于 的元素。若 等于较小部分的大小加一,则返回 。否则,在相应的部分上递归,并在丢弃较小部分与主元之后相应调整 。元素互异使这三个部分没有歧义;若要处理重复元素,则需要另行进行等键划分并检查秩。
定理
定理 1.10.2
(主元丢弃界)
对于 ,原列表中至少有 个元素不小于主元,且至少有 个元素不大于主元。因此,两个严格划分部分的大小都至多为 。
定理 1.10.3
(正确性与线性最坏情况工作量)
该算法返回秩为 的元素。在固定大小的分组排序和线性时间划分的前提下,其最坏情况比较次数为 。
证明思路或证明
证明
(计算主元两侧的元素)
至少有 个组中位数不小于这个作为主元的中位数(计入主元本身),也至少有 个不大于它。至多有一组是不完整的。每个中位数不小于 的完整组都至少含有三个不小于 的元素;这些组两两不相交。因此至少有 个元素不小于 。对另一侧应用同样的论证,即得较小一侧的界。这一计数包含了主元本身,这已经足够:严格较小的部分排除了所有不小于 的元素,严格较大的部分同理。
证明
(正确性与线性递推式)
关于正确性:划分给出主元在当前列表中的准确秩。若目标秩等于该秩,则主元即为答案。否则,被丢弃一侧的所有元素与主元都已知位于目标的同一侧。在剩余列表上以相应的秩递归,所求元素得以保留。子问题的规模不断缩小,而固定大小的基础情形由排序正确处理,因此对列表大小作归纳即证明了正确性。
对每组排序只需常数工作量,因为组的大小至多为五;共有 个组,而划分的代价为 。设 为所有大小至多为 的合法输入上的最坏比较次数,因此它是非递减的。于是对某个常数 以及 ,
第一次递归调用用于选取主元,第二项则是所探索的那个划分部分的上界。对于归纳界 ,两个递归规模之和至多为 。当 时,;取 ,并使其足够大以涵盖有限多个基础规模。则 。归纳法证明了 。
证明透视
两次递归调用,却只有一次划分
递推式的每一项各有来源。 是从各组中位数中选取主元的那次调用; 是其后所探索的唯一一个划分部分,并非两个部分都探索,因为目标至多位于一侧。分组大小五给出比例 ,主元丢弃界给出 。两者之和为 ,这个约为 的十分之一的缺口,正是用来支付线性工作量 以及 时的附加项 。关键的一步是对两个规模同时使用归纳假设,得到 。
去掉任何一个成分,论证都会失效。若改为每组三个元素,两个比例约为 与 ,和约为 ,没有缺口来吸收 。因此证明依赖的是这两个具体的比例,而不只是存在两次较小的调用。
例题详解
例题 1.10.4
(秩的更新)
假设对九个互异元素进行划分,主元 之下有四个元素,之上也有四个元素。主元的秩为五。要选取秩为七的元素,丢弃四个较小的元素和 ;所求元素在四个较大元素中的秩为 。
例题 1.10.5
(组中位数证书)
对于已排序的一组 ,其中位数为 。若主元至多为 ,则该组中的 这三个元素不小于主元。若主元至少为 ,则 这三个元素不大于主元。证明中正是对不相交的完整组累计这一局部事实。
例题 1.10.6
(为什么端点主元有风险)
若快速选择始终选取最小元素作为主元,而所求的是最大元素,则每一步只丢弃一个元素。划分工作量之和为 。中位数的中位数方法的界排除了大规模调用中这种持续的失衡。
常见错误
反例模式
选取中位数的中位数不等于选取真正的中位数
一个诱人的说法是:主元就是整个列表的中位数。取 ,分成 、 和 三组。各组中位数为 ,所以中位数的中位数是 ,而这十五个数的真正中位数则是 。按所述实现,这个小列表会走基础情形;这里的例子只是单独展示主元的构造。因此证明并不假设主元恰好处于正中间的秩,只要求较弱的保证:主元在两侧都至少留下 个元素。
常见错误
(计入不完整的组)
不完整的组在其中位数的某一侧可能含有不足三个元素,因此在必要时必须将其排除在每组三个元素的计数之外。这正是界中要减去一组的原因:得到 ,而不是 。
常见错误
(害怕两次递归调用)
含有两次递归调用的递推式并不会自动导致超线性。这里两次调用的规模之和至多为 ,留有余地来吸收线性工作量。只有当规模之和达到 时,论证才会失效。
秩的界从何而来
证明计数的是组,而不是寻找主元时实际进行的单次比较。列表被分成互不相交的组,因此某一组中被证实的三个元素不可能同时被算作另一组的元素。当某个完整组的中位数不小于 时,该中位数及其之上的两个元素都不小于 。当其中位数不大于 时,该中位数及其之下的两个元素都不大于 。我们分别对两侧计数;像主元这样的元素可以同时计入两个非严格计数,这无妨,因为每个计数所界定的是不同的严格划分部分。
共有 个中位数,其中包括可能存在的不足额末组的代表。即使 为偶数,这些代表的下中位数也满足:至少一半的代表不大于它,至少一半不小于它。每一侧被证实的组中至多有一个是不足额的,因此减去一个完整组即得安全的下界。这一估计牺牲了一些本来有效的元素,但线性时间的证明只需要常数比例,而不需要最佳的加性常数。
主元本身是原有元素之一。在实现中,找到它之后可以将其移动或复制到单独的变量中,但划分时仍须将它恰好计入一次。若有 个元素严格较小,则主元的秩为 。当 时,丢弃这 个较小元素和主元,在较大部分中的目标秩为 。由于 ,这个新的秩落在较大部分之内。当 时,原来的秩在较小部分中本就有效。
递推式为何闭合
选取主元的那次调用至多处理 个元素。被选中的划分部分至多含有 个元素。因此二者之和至多为 。其中的加性常数四并未被忽略:当 时,所节省的十分之一的 比它至少多出 。再取一个足够大的归纳常数,以支付线性的非递归工作量,估计便得以闭合。有限多个较小的输入则通过增大同一个常数来涵盖。
证明将 定义为大小至多为 的输入上的最坏代价,使其成为非递减函数。这样,规模未知的递归调用就可以用 在规模上界处的取值来界定。若 仅对恰好 个元素的输入定义,则单调性需要另行论证。定义这个单调包络使不等式一目了然,并且对任何具体输入都不会削弱最终的上界。
该递推式是最坏情况下的不等式,而非精确的等式。主元可能立即返回,被选中的划分部分可能小于上界,各组的排序也可能用到更少的比较。为了得到上界,我们为每次调用的分组、排序与划分各计入固定的线性工作量。证明并不声称每次执行都恰好用 次比较,也不声称这些常数能与实际中的随机化选择算法相竞争。
比较模型与下界
定理统计的是元素之间的比较次数,并把移动或索引元素视为常数工作量。固定大小的基础情形可以使用任何正确的排序方法;由于它处理的元素少于一百个,其最坏代价被一个绝对常数所界定。若比较本身代价高昂,则每次比较的代价必须另行计入。内存使用和数据移动同样是独立的资源:本证明是在所述模型下关于比较次数与线性工作量的上界。
求最大值说明了为何线性工作量是自然的目标。在比较模型中,除最大值之外的每个元素至少要输掉一次比较;否则,一个从未输过的元素在与已观察到的结果相容的某个全序下仍可能是最大值。每次比较至多产生一个输家,因此最坏情况下至少需要 次比较。所以,选择算法的 界对于求最大值这一实例而言是渐近最优的。这个论证并不需要对整个列表排序。
重复键与模型边界
元素互异的假设使主元可以独立成一部分。若存在重复键,正确的改写应将列表划分为小于、等于和大于三个区域。若所求的秩落在等于区域之内,则返回该公共键;否则在某一严格侧上以调整后的秩递归。完整的证明必须修改计数与划分的论证,以顾及相等的元素。本单元陈述的是互异元素的定理,而不是悄悄依赖一种可能反复保留大量相等键的二路划分。
反例模式
重复键会使互异元素算法失效
一个诱人的说法是:键重复时算法无须修改仍然成立。取 个相同的键,。主元 就是这个键,因此没有元素严格小于或严格大于它:两个严格部分都是空的,秩 不等于 ,也没有可供递归的部分。三路划分的修正办法,是把列表分成小于、等于和大于三个区域,并在秩落在等于区域之内时返回该公共键。
固定的五元素分组对算术也很关键。把五换成其他大小,会同时改变选取主元那次调用的规模和所保证的丢弃比例。不重新计算这些量,就不能照搬不等式 。一般的策略比这个特定选择更为宽广,但具体的证明属于所述的分组与代价模型。
总结
秩受到控制的主元使得一次划分中的一侧可以被丢弃。按五个一组分组给出了固定比例的保证,而递归地选取主元则需要再花费一次规模更小的调用。这两个规模上界加上线性的划分工作量,得出线性的最坏情况比较次数。
练习
快速检查
(某主元之下有七个元素。它的秩是多少?)
别忘了主元本身。
解答 · 答案
它的秩是八:有七个较小的元素排在它前面。
快速检查
(若所求的秩为十,而主元的秩为八,则在较大的元素中要找的是第几名?)
数一数被丢弃的元素有多少个。
解答 · 答案
目标是比主元大的元素中第二小的一个,因为包括主元在内的八个元素已被丢弃。
快速检查
(为什么至多只有一组不完整?)
想想列表是怎样被切成各组的。
解答 · 答案
把列表按顺序每五个分成一组;只有最后一组可能不足五个元素。
快速检查
(为什么对每组排序仍然只是线性工作量?)
同时计算每组的成本和组数。
解答 · 答案
每组至多有五个元素,所以排序一组只需固定次数的比较;组数为 。