比较排序下界

这是一条排序专用的信息论下界：算法必须区分 $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 · Comparison decision tree用查询节点、答案分支和输出叶刻画算法能够区分输入所需的信息深度。固定了本页每步能问什么，对手下界方法公理库对手下界方法Adversary lower-bound method · Adversary argument以全局一致的延迟回答维持多个候选输入，证明有限查询无法区分所需输出的方法。则把“延迟承诺输入、始终返回合法回答”推广到不能只数叶子的场景。在 $n$ 元有序表中定位元素需要 $\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)$，但这项组合推论并不排除整数键、随机化或其他更强原语。