动机
快速排序选取一个主元,将其余元素围绕它划分,然后递归地对两侧排序。如果每一步都恰好选到很差的主元,就会产生二次方的工作量。随机选取主元并不能排除这种执行过程,但它使我们能够对任意固定输入,就算法自身的随机选择来量化其平均代价。
我们不直接求解递推式,而是提出一个更局部的问题:对于已知排序名次的两个元素,它们在整个执行过程中被比较的概率是多少?把这些概率相加,即得到期望比较次数的精确值。证明还说明了为什么各个键对比较事件之间不需要独立性。
定义
定义 1.9.1
(配对指示变量与比较次数)
输入由比较模型中的 个互不相同的键组成。在每个含有 个键的递归调用中,从这些键中均匀随机地选取一个主元;在给定当前子问题的条件下,该选择与以往的随机选择相互独立。将该子问题中其余每个键各与主元比较一次,把较小的键放在一侧、较大的键放在另一侧,然后递归地对两侧排序。规模为零或一的调用不进行任何比较。
设排序后的键为 。对每个 ,若 与 在执行过程中被比较,则令 为一,否则为零。设 为按上述划分规则所作的键比较总次数。当 时记 ,并规定 。
定理
定理 1.9.2
(键对比较概率)
对每一对 , 与 被比较的概率为 。
定理 1.9.3
(期望比较次数的精确值)
对 ,随机化快速排序的期望键比较次数为
其中约定 。特别地,该期望为 。
证明:哪个主元会分隔一对键?
证明
(只有区间中的第一个主元才起作用)
考虑名次区间 。在该区间内没有任何键被选为主元之前,区间内所有键始终留在同一个递归子问题中。名次较小的主元会把整个区间送往较大的一侧;名次较大的主元会把整个区间送往较小的一侧。因此,区间之外的主元不可能把两个端点分开。
当区间内的第一个主元被选出时,有两种可能。若它是 或 ,则另一个端点处于同一子问题中,并与该主元比较。若它是内部的键,则两个端点被送入相反的递归子问题,此后永远不会被比较。任何一对键至多被比较一次,因为其中一个端点被选为主元之后,就不再出现在递归调用中。
区间内第一个被选中的主元在其 个键中服从均匀分布。理解这一点的一种方式是:预先给键分配一个均匀随机的优先级顺序,并始终以子问题中优先级最小的键为主元。这样得到的主元在每个当前子问题中都是均匀的,而且任意固定子集中优先级最先的键属于其中任一成员的可能性相同。等价地说,对区间之外的主元反复取条件,并不破坏区间内各键之间的对称性。区间内恰有两个键是端点,因此所求概率为 。
证明透视
区间内的第一个主元
名次区间之外的主元使两个端点保持在一起。端点作主元时完成它们唯一的一次比较;内部的键作主元则将它们永久分开。区间内各键之间的均匀对称性因此把概率计算归结为:在区间大小所对应的键数中,有两个有利的键。
证明:对指示变量求和
证明
(对配对概率求和)
每次比较都发生在一个主元与另一个键之间,且没有任何一对键被比较两次。因此 。由期望的线性性(它并不要求这些指示变量相互独立),
对于区间长度 ,具有该区间长度的键对共有 个。因此,当 时,
当 时,按约定两边都为零。对 ,积分界 给出渐近上界。调和和的增长阶也至少为 ,因此当 足够大时,期望比较次数为 。
正确性与代价模型
在每个递归调用中,放在主元左侧的每个键都较小,放在右侧的每个键都较大。对子问题规模用归纳法可知两个递归结果都已排好序;把排好序的左侧、主元与排好序的右侧串接起来,就得到按顺序排列的全部输入键。每次调用都把其主元从后续递归中移除,因此对任何主元序列算法都会终止。
该精确定理计算的是在所述划分过程下的键比较次数。若划分对每个被检查的键只做常数量的额外工作,且主元可在常数时间内采样,则在该模型下总的期望运行时间为 。具体实现必须自行计入主元生成的代价与存储。该期望是对固定输入上的随机主元选择而取的;它并不假定输入本身是随机排列的。
最坏的主元序列是反复选取最小值或最大值,此时共进行 次比较。不利情形出现的概率也许很小,但期望界并不禁止它发生。
概念视角结构
递归树是一棵随机二叉搜索树
把每个主元记为其子问题的根,两侧子问题的主元作为它的子节点。这是 上的二叉搜索树,而每个键与其上方的每个主元恰好比较一次。因此 当且仅当 之一是另一个的祖先,而 就是所有节点深度之和(根的深度为零)。上文的期望就是总深度的期望;当 时为 。
例题详解
例题 1.9.4
(两个键)
当 时,无论哪个键成为主元,都恰好与另一个键比较一次。公式给出 ,与直接计数一致。
例题 1.9.5
(三个键)
当 时,中位数以概率 首先被选中,此时进行两次比较,之后不再有比较。端点以概率 首先被选中,此时进行两次比较,随后再对其余两个键进行一次比较。期望为 。公式给出 。
例题 1.9.6
(一对端点)
在五个已排序的键中,最小者与最大者只有在这两者之一是全部五个键中第一个被选中的主元时才会被比较。它们被比较的概率为 。选到中间的主元则会立即把它们分开。
例题 1.9.7
(一次最坏情形的执行)
对于五个键,设在每个非平凡调用中都选中剩余键中最小者。划分比较次数为 。尽管其期望次数更小,这仍是该随机化过程的一种可能执行。
常见错误
反例模式
期望并不意味着每次运行都如此
对三个键,先选端点会产生三次比较,而先选中位数则产生两次比较。期望次数为 ,它既不是每次执行的上界,也不是任何一次实际执行的比较次数。
常见错误
(把比较指示变量当作相互独立)
比较指示变量一般是相互依赖的。若某个内部主元将一对键分开,它同时也影响了其他哪些键对以后还能被比较。即使没有任何独立性假设,各期望之和仍然成立。
常见错误
(对输入而非主元取平均)
期望是对算法的主元选择而取,不是对输入而取。若采用确定性规则,例如永远以第一个键作主元,在已排序的输入上会做 次比较,因为每个主元都是其子问题的最小元。界 对每个固定输入都成立,正是因为只有主元是随机的。
反例模式
相等的键会使精确公式失效
设键并不互不相同,且划分规则把所有不大于主元的键放到左侧。取 个相等的键。无论哪个键作主元,其余两个都与它比较并全部进入左侧;规模为二的左侧再花一次比较。每次执行都恰好做 次比较,而互不相同键的公式给出 。键对概率 不再适用,因为没有任何键严格小于另一个。修正方式是假设键互不相同,或另行分析具体的相等处理规则;附加破平标识只有在比较确实使用这些标识时才有帮助。双路与三路实现对重复键的处理各不相同,其精确比较次数需要另行分析。
为什么随机优先级的观点成立
对全部键作一个均匀随机排列,可以看作给每个键分配一个唯一的优先级。任一非空集合中优先级最先的键,等可能地是该集合中的任一键。某个主元被确定后,其余键的相对优先级顺序仍然是均匀随机的。把该顺序限制到任一递归侧,所得条件分布与在该侧重新作均匀主元选择相同。
这种耦合是一种证明手段,并不要求实现真的生成完整的排列。它使我们即使在区间之外的主元更早被选出时,也能讨论名次区间内的第一个主元。区间内优先级最先的成员在其成员中是均匀的,而在它出现之前,每个区间之外的主元都使该区间保持在一起。
精确计数依赖于这样的规则:每个非主元键与其主元恰好比较一次。划分的实现可能做额外的键比较,例如在执行某些边界检查时。它们仍可用类似的思想分析,但在未核对实际比较规则之前,不应原样照搬所给的等式。
一个具体的四键计算
对四个键,名次相邻的键对有三个。每一对必然被比较:没有任何内部键能分隔相邻名次,而该键对中第一个被选中的主元必是某个端点。名次区间长度为三的键对有两个,各以概率 被比较;区间长度为四的键对有一个,以概率 被比较。求和得
调和数公式给出相同的数值,因为 ,且 。这一计算数的是键对事件,而不是独立的硬币投掷。有些比较可以同时发生,而数值 不必是任何一次具体运行中的比较次数。
最不平衡的序列有多罕见?
对 ,取得最大比较次数的执行,在每个规模至少为二的子问题中都选取最小键或最大键。在规模为 的调用中,选到两个极端之一的概率为 。在此前所有选择都是极端的条件下,剩下的唯一非平凡调用的规模为 。把这些条件概率相乘得
当 时该概率为一;当 时为 ,与前面的直接例子一致。反之,非极端的主元会产生两个非空的侧,并使之后可能的最大比较次数低于仅剩一个子问题的情形。因此,对互不相同的键,在这一划分规则下,所描述的事件恰好就是比较次数取最大值的事件。尽管其概率迅速减小,但对每个有限的 它都是可能发生的。
调和数估计的两个方向
对 , 可这样得到:对 ,把每个倒数 与 在 上的积分作比较。对于下界,把各项分成若干块:从 到 的各项,每项至少为 ,共有 项。因此每个完整的块至少贡献二分之一。到 为止的完整块的个数与 成正比地增长。
把这些界代入精确公式,即可解释渐近增长。负的线性项不改变阶:当 足够大时,调和数因子超过某个固定正常数的量,像 一样增长。对于小规模输入,精确表达式的信息更丰富,因为渐近记号会掩盖相当大的差异。
键对的概率取决于名次与区间长度,而不取决于输入最初的排列。在均匀选取主元与这一比较规则之下,由相同的互异键构成的每个固定排列,其期望次数都相同。这种对称性是随机化算法本身的性质,并不保证现实中的输入是均匀随机到达的。
总结
两个键被比较,当且仅当其中之一是两者名次之间(含端点)各键中最早的主元,这发生的概率为 。对键对指示变量求和,得到精确的期望及其 的增长阶,而个别执行仍可能是二次方的。
练习
快速检查
(计算名次 与 被比较的概率。)
解答 · 答案
它们的名次区间长度为三,所以概率为 。当名次 或名次 是名次 中第一个被选中的主元时,它们被比较。
快速检查
(对四个键,在所述规则下,比较次数最多可能是多少?)
解答 · 答案
反复选取极端键给出 次比较,而任何执行都不会超过这个数:第一次调用进行三次比较,并把其余三个键分在两侧。若三个键全在同一侧,之后至多再比较 次;若分成规模为二与一的两侧,至多再比较 次。因此总数至多为 。
快速检查
(为什么两个键至多被比较一次?)
解答 · 答案
比较发生在这对键中的一个被选为主元时。该主元不会出现在之后任何递归调用中,因此这一对键不会再次被比较。
快速检查
(解释为什么即使指示变量 可能相互依赖,期望的线性性仍然适用。)
解答 · 答案
对有限和,不论是否相互依赖,期望都对加法分配:。独立性与某些乘积的计算有关,但在这里并不需要。