比较排序下界

这是一条排序专用的信息论下界：算法必须区分 $n!$ 种相对次序，而一次二元比较只产生一个 bit 的分支。逐次维持合法回答、延迟承诺具体输入的通用证明方式见对手下界方法理路对手下界方法Adversary lower-bound method · Adversary argument以全局一致的延迟回答维持多个候选输入，证明有限查询无法区分所需输出的方法。；本页只使用叶数计数。把比较看成返回一位答案的 oracle query 时，这也是查询下界理路查询复杂度模型Query complexity model · Bit-query model将输入隐藏在坐标 oracle 后，只统计算法为确定函数值而读取的输入位置数量。的一个特例，但结论只约束这种访问接口。Word-RAM 可以读整数位并把键值用于寻址；通信模型理路两方通信模型Two-party communication model · Two-party communication complexity model两位参与者各自持有私有输入，只以交换消息协同计算函数或关系，并把通信位数作为核心资源。计算双方交换的 bit；外存模型计算块传输。三者的单步信息与资源单位都不同，不能直接继承这棵比较树的高度下界。

小规模可以完全算清：$n=3$ 时 $\lceil {\log }_{2}6\rceil =3$，故任何比较排序最坏至少 $3$ 次比较；插入排序恰以最坏 $3$ 次完成三元素排序，说明该下界在小规模处可以取到。渐近方向，归并排序理路归并排序Merge sort递归排序两半并线性合并的稳定比较排序算法。与基于二叉堆理路二叉堆Binary heap用完全二叉树形状与父子堆序维护极值、常以数组隐式表示的数据结构。的堆排序都只用 $O(n\log n)$ 次比较，与下界匹配，因而在比较模型中渐近最优。

边界之一：绕过模型不算违反下界。计数排序理路计数排序Counting sort对有限整数键频数计数并按前缀位置输出的线性时间非比较排序。直接把键值当下标使用，时间 $O(n+k)$；基数排序理路基数排序Radix sort按稳定子程序逐位处理固定长度键的非比较排序。按数位分配，时间 $O(d(n+k))$——对范围在 $[0,n^2)$ 内的整数取基数 $n$ 只需两趟，总计 $O(n)$，胜过 $n\log n$ 而与定理无矛盾，因为它们不做两两比较。之二：下界针对互异键的最坏（或均匀平均）情形；若键只有 $k$ 种取值或输入接近有序，可区分的输出减少，自适应算法确实能少比较，但对一般互异输入，任何比较排序都无法整体逃出该界。之三：计量对象是比较次数，搬移、缓存等开销另算——不过在比较模型中总运行时间不低于比较数，故时间下界随之成立。

决策树模型理路决策树模型Decision-tree model用查询节点、答案分支和输出叶刻画算法能够区分输入所需的信息深度。固定了本页每步能问什么，对手下界方法理路对手下界方法Adversary lower-bound method · Adversary argument以全局一致的延迟回答维持多个候选输入，证明有限查询无法区分所需输出的方法。则把“延迟承诺输入、始终返回合法回答”推广到不能只数叶子的场景。在长度 $n$ 的先假后真谓词序列中，有 $n+1$ 个可能分界；每次只询问一个位置的真假，最坏至少需要 $\lceil {\log }_2(n+1)\rceil$ 次询问。二分查找理路二分查找Binary search在有序数组中反复排除一半候选区间的查找算法。的分界版本达到这个界。精确成员查找若采用三路比较，应另按其允许分支论证，不能直接套用这句精确常数；前驱问题理路Word-RAM 前驱问题Predecessor problem在 Word-RAM 的有限整数宇宙中维护有序集合，并查询不大于给定键的最大成员。若仍只允许比较也受相似障碍，但 Word-RAM 可读取整数位，因此必须另看对应模型的上、下界。

把排序归约到另一个问题，才能把排序下界传递给该问题，并且必须保持所用计算模型：把数 $x_i$ 提升为抛物线上的点 $(x_i,x_i^2)$ 后，平面凸包理路凸包Convex hull包含给定点集的最小凸集，是凸几何中的基本包络对象，并可进一步研究其算法构造。的有序顶点序列能读出排序；输出起点和方向可在线性时间内整理。但一般凸包算法允许几何谓词，不能仅凭这次变换就把二元键比较树的下界搬过去，需在相应的代数决策树模型中另证排序下界。

外存中的瓶颈是块传输，排序 I/O 下界理路外存排序 I/O 下界external-memory sorting lower bound · I/O sorting lower bound在原子记录的两层 I/O 模型中，排序需要与多路归并上界匹配的块传输次数。需要同时计 $N,B,M$，不能从 $\mathrm{\Omega }(n\log n)$ 次比较除以块大小得到。

用比较型优先队列先插入全部互异键，再逐次取最小，就能完成排序。因此插入与取最小不能都具有摊还 $o(\log n)$ 的保证；零错误随机化也不能让插入和取最小在所有输入上同时具有期望摊还 $o(\log n)$，因为排序的期望下界仍适用。整数键或其他更强原语则改变了模型。