动机
合并排序和堆排序在最坏情况下使用 次比较。这一代价只是这两种算法的偶然现象,还是所有基于比较的排序方法都无法绕开的障碍?决策树把算法可能出现的各种比较结果转化为一个计数问题:必须存在足够多不同的结果,才能区分各种可能的输入顺序。
模型的选择至关重要。当键值落在适当小的整数范围内时,计数排序可以在线性时间内运行,因为它利用键值作为数组下标。下界假设比较是获取键值顺序信息的唯一途径,因此计数排序并不是该下界的反例。
定义
定义 1.8.1
(确定性比较排序算法)
确定性比较排序算法接收 个互不相同的键,并且对每一种输入顺序都必须按递增顺序输出这些键。其控制流可以依赖于键与键之间两两比较的结果。我们统计的是键的比较次数,而不是移动次数,也不是与键值无关的算术运算。对于互不相同的键,一次比较有两种可能的结果:小于或大于。
定义 1.8.2
(比较排序的决策树)
比较决策树中,每个内部节点对应算法在该时刻可能进行的一次比较,每种结果对应一条出边。叶子记录在观察到相应结果之后所选定的输出顺序。不同分支的长度可以不同;从根到叶子的最大长度即最坏情况下的比较次数。
定理
定理 1.8.3
(比较排序需要大量比较)
对 个互不相同的键进行排序的每个确定性比较排序算法,都存在一个最坏输入,至少需要 次比较。因此其最坏情况比较次数为 。
定理 1.8.4
(有界整数键的计数排序)
对于取值于 ()的 个整数键,在下文所述的数组下标模型中,计数排序可以在 时间和 辅助空间内产生稳定的有序输出。
证明:统计叶子数
证明
(统计决策树的叶子)
个互不相同的输入位置共有 种可能的相对顺序。正确的比较算法必须区分所有这些顺序。如果两种不同的相对顺序到达同一片叶子,算法对二者就会输出相同的输入位置排列。由于这两种顺序对应的正确递增位置排列不同,至少有一个输出是错误的。
高度为 的二叉树至多有 片叶子。即使某些叶子出现在深度小于 处,这一结论仍然成立:可以在概念上把每条较短的路径延伸到深度 ,也可以用归纳法证明该界。因此,对全部 种顺序都正确的决策树必须满足 ,从而 。
要得到初等的渐近界:当 时, 的因子中至少有 个不小于 。于是 ,其以 2 为底的对数为 。上界 则由每个因子至多为 得出。因此信息量需求的量级为 。
证明透视
为什么两种顺序不能共用一片叶子
证明有三个环节。第一,叶子只固定一个输出排列,因为算法只看到了通往该叶子的路径上的比较结果。第二,键互不相同,所以不同的相对顺序需要不同的输出排列;用到“互不相同”的正是这一步。因此至少存在 个不同的叶子。第三,把计数转成时间界的是 :二叉树至多有 个叶子,所以叶子很多就迫使高度很大。
每个环节都可以问:少了它会怎样。若算法可以直接读取键值(而不只是比较),叶子就不再由一串二元结果组成的路径决定,叶子的数目也就不能限制运行时间。若允许相等的键,需要的不同输出便少于 个。证明并没有指出较深的叶子在哪里,只说明存在这样一个叶子。
计数排序与稳定性
定义 1.8.5
(稳定排序)
若一个排序算法在输出中保持键相同的记录在输入中的相对顺序,则称它为稳定的。
对每个键值 ,统计输入中有多少项具有该键值。计算前缀总和 ,即键不超过 的项数。从右到左扫描输入。对于键为 的一项,以零为起始下标,把它放到输出位置 ,然后将 减 1。
证明
(计数排序正确、稳定,代价为 O(n+K))
为键 预留的位置恰好是一段连续区间,位于所有较小键的位置之后、所有较大键的位置之前。每一项占用该区间内一个尚未使用的位置,因此输出是有序的,且每个输入项恰好出现一次。从右到左扫描会从右到左填充该区间:若两个键相同的项在输入中以某一顺序出现,则靠后的那一项被放在靠后的输出位置。它们的相对顺序得以保持,这就是稳定性。
初始化计数数组和计算前缀总和的代价为 ;计数和输出放置的代价为 。计数数组使用 空间,输出数组使用 空间。这里假定按键索引的代价为常数时间,并且保证键是所述范围内的整数。范围大小 是代价的一部分:若 相对于 非常大,该算法不一定比比较排序更快或更省空间。
例题详解
例题 1.8.6
(三个互不相同的键)
共有 种可能的顺序。高度为 2 的二叉比较树至多有四片叶子,所以某些输入至少需要 次比较。三次比较总是足够的,例如先比较两个键,再把第三个键插入到它们已排好的序对中。
例题 1.8.7
(对一个小数组计数)
对于键 且 ,键值 的计数为 。前缀总和为 。它们预留的输出位置是:键 0 占位置 ,键 1 占位置 ,键 2 占位置 。输出的键为 。
例题 1.8.8
(相等的键保持原有顺序)
设上例中两个键为 2 的项按输入顺序分别标记为 和 。从右到左扫描时,先把 放在位置 3,之后把 放在位置 2。它们的输出顺序为 ,所以相关记录保持稳定。
例题 1.8.9
(范围很大会改变得失权衡)
当 且保证键在大小为 的范围内时,计数数组需要十亿个条目。 这一界是正确的,但其中的 项占主导地位。比较排序则可以避免为每个可能的键值分配一个计数器。
常见错误
反例模式
线性时间的整数排序并不反驳决策树下界
一个诱人的说法是:每个排序算法都需要 步。计数排序在键范围很小时就推翻了它。取 个键,取值于 ,即 。计数排序的步数为 ,而 ,所以比较排序在某些输入上至少需要 次比较。这并不矛盾,因为决策树的证明只统计对键的二元比较,计数排序却把每个整数键当作数组下标来读取,一步操作就能在 个值之间作出区分。它获得了比较模型以外的信息,所以下界的假设并不适用。正确的说法是受限制的版本:只靠比较来排序任意互不相同的键,需要 次比较。
常见错误
(最坏情况下界不是对每个输入的下界)
最坏情况比较次数的下界并不表示每个输入都需要那么多次比较。自适应算法可能很快识别出某些已经有序的输入,却仍然在另一个输入上需要大量比较。该下界也没有计入移动大型记录或分配内存所花费的时间。
常见错误
(计数 n! 默认键互不相同)
下界使用互不相同的键,以保证有 种不同的所需相对顺序。相等的键会减少可区分顺序的数目,而稳定性对键相同的记录另有要求。对于必须处理所有输入的算法,这族互不相同的困难输入已足以确立最坏情况下界。
模型揭示了什么
决策树抽象掉了算法选择的具体比较。一个算法可能比较相邻的键,另一个可能比较相距很远的键,它们的树形状可以大相径庭。叶子数同时约束所有这些算法,因为每个二元结果至多使可区分的分支数加倍。
证明并不要求树是平衡的。某个输入对应的叶子很浅,就会使可供其他众多顺序使用的浅路径变少。高度界说明至少有一条路径很长,但并没有指出对于具体某个算法,哪个输入会实现这条路径。
对于有界整数键,模型提供的不止是比较。键值直接选定 个计数器之一,而算法要为这些计数器的初始化和遍历付出代价。这两种分析可以并存:一种证明了在对键的访问受限时的局限,另一种利用更强的操作并核算其内存范围。
概念视角分析
连常数也保留的同一个界
Stirling 公式给出
所以信息界是 ,而不只是 。当 时右边约为 ,与上文所用的值吻合。
平均深度与随机算法
同样的计数思想也可以约束在均匀随机输入顺序上的平均比较次数。设 种可能的顺序终止于深度为 的叶子。对于任意二叉树,叶子权重满足 。一种证明是:给根赋权重 1,并把每个节点的权重平均分给它的两个子节点;所有叶子的权重之和至多等于初始权重。
算术-几何平均不等式给出
取以 2 为底的对数并整理,得到 。因此,对于每个确定性比较排序,即使在均匀选取的互不相同键的顺序上取平均,也至少需要 次比较。这比仅仅说有一条路径具有该长度的结论更强。
现在考虑一个随机化比较排序,它对每个输入和每种随机选择都正确,并且比较次数和随机比特数都有固定的有限上界。固定其随机比特:得到的确定性比较树仍然对每种输入顺序正确排序。它在均匀输入分布下的平均深度至少为 。对随机比特取平均保持这一不等式。因此,至少存在一个固定的输入顺序,其期望比较次数至少为 ,其中剩余的期望是对算法自身随机选择取的。这一论证并不声称每个输入都有这样的期望代价。
比较次数和随机比特数都有固定的有限上界,使得所有平均都是普通的有限和。更一般的几乎必然终止的随机化算法可以借助额外的极限论证来处理,但这里陈述的版本并不需要这些。均匀分布只是用来找出一个困难的固定输入的证明手段,并不是对现实世界输入所作的假设。
记录与取值范围编码的代价核算
计数排序通常用来排序带有附属数据的记录,例如附在整数分数上的姓名。稳定性针对的正是这些记录:分数相同的记录必须保持其原有顺序。计数数组存放各键值的计数;输出数组存放记录或指向记录的引用。如果复制整条记录的代价超过一个单位,就必须把这一表示细节计入操作代价。
参数 是键的全集的大小,而不是恰好出现的互异键的个数。如果键的范围从已知的整数最小值 到最大值 ,减去 后得到从 0 到 的下标,数组长度为 。计算或存储一个巨大的范围,其代价可能超过输入规模。在位模型中,表示一个键并对其做算术运算的代价也可能超过一个单位;所述的界针对的是字级数组下标模型。
比较算法可以利用特定输入中已有的顺序,整数算法可以利用较小的键全集。这是两种不同的结构来源。只要任意互不相同的键只能通过二元比较来排序,最坏情况下界就依然适用,即使个别输入恰好很容易。
当 或 时,只有一种相对顺序,下界为零次比较。渐近陈述针对的是 增大的情形,并不要求在零处计算 。类似地,当 时,计数排序可以直接返回空输出,但仍需为任何显式初始化的计数数组付出代价。
总结
比较排序的决策树必须有足够多的叶子来区分 种顺序,由此得到最坏情况 的比较次数下界。计数排序在另一种模型下利用整数的直接下标,以 时间运行,并通过反向遍历获得稳定性。
练习
快速检查
(高度为四的二叉决策树至多有多少个叶子?)
每一层至多使分支数加倍。
解答 · 答案
至多 个。有些叶子可能位于较小的深度,但这不会使最大值增加。
快速检查
(对四个互不相同的键排序,叶子论证给出什么下界?)
数出相对顺序的个数,再与二的幂比较。
解答 · 答案
共有 种相对顺序。由于 ,某些输入至少需要五次比较。
快速检查
(对于键 ,给出计数数组和排序后的键序列。)
键范围为 ,即 。
解答 · 答案
对于键范围 ,计数为 ,排序后的键为 。
快速检查
(为什么在计数排序中从右到左扫描输入能保持键相同的记录的顺序?)
想想键相同的记录中哪一个先被放置。
解答 · 答案
随着前缀计数器递减,每个键的输出区间从右到左被填充。输入中较后的记录先被遇到,并获得较后的位置,所以较前的记录在输出中仍然较前。