一个算法已经做到O(n log n)，不代表所有模型都不可能更快。下界必须说明算法能观察什么、存储多少信息、允许哪些操作，以及成本怎样计量。删掉这些条件，下界很容易变成错误的性能承诺。

本篇完整推导比较排序的基础下界，再把整数前驱与单遍流放回各自模型中。29篇的NP困难性依赖归约与尚未解决的类别关系；下面的比较决策树下界则可以直接从信息量证明。两种论证不能混为一谈。

比较排序必须分辨n!种次序

输入为n个互异键，算法需要输出它们的升序排列。模型只允许通过两键比较获取次序信息，不能把键当数组下标、拆出整数位，或通过键的数值计算直接推断位置。其他搬移操作不计入下面的比较次数下界。

固定一个确定性算法，把每次比较视作一个内部节点。因为键互异，比较结果只有“小于”和“大于”两个分支。一次完整执行对应根到某个叶子的路径，路径长度就是该输入所做的比较次数。

n个带身份的输入位置共有n!种可能的严格大小次序。一个叶子固定了算法最后输出的位置排列；同一个输出排列不能同时正确处理两种不同的严格次序。因此正确算法的决策树至少需要n!个叶子。

深度至多h的二叉树最多有2^h个叶子，所以最坏输入的比较数满足h≥⌈log₂(n!)⌉。对n≥2，n!中至少n/2个因子不小于n/2，得到

log⁡2(n!)≥n2log⁡2n2=Ω(nlog⁡n).\log_2(n!)\ge\frac n2\log_2\frac n2=\Omega(n\log n).

结合归并排序的O(n log n)比较上界，比较模型中的最坏渐近量级已经匹配。这里没有使用“运行了很多排列都很慢”作为证据；叶子数量约束覆盖全部合法输入。

这个下界没有说什么

它说存在某个最坏输入需要这么多比较，不是每个输入都需要。带有已排序检查的算法可能在某些输入上只比较n−1次，然后立即返回；这不违反最坏下界。

模型还固定了互异键与任意输入次序。若承诺只有少数取值，或者输入已经满足额外有序结构，算法需要区分的状态数量会变。不能在改变输入集合后继续机械地使用n!个叶子。

20篇的整数排序能读取数字位，已经超出纯比较模型。计数排序对范围[0,U)的整数可用O(n+U)操作，但付出O(U)计数空间；U极大时这并不划算。它不是推翻比较下界，而是使用了下界模型禁止的信息访问方式。

对随机算法也要先说保证。本节完整证明的是确定性最坏比较数；“随机种子固定后是一棵树”本身不能把存在坏输入直接交换成某个固定输入上的期望下界。若要证明随机期望下界，还需分布或平均深度论证，本篇不把它当作已经证明的结论。

整数前驱需要列出更多变量

整数前驱查询给定集合S及查询整数x，返回S中不大于x的最大值；不存在时返回空。20篇的教学接口采用严格前驱“小于x”；此处按所引论文采用“不大于x”，键相等时答案不同，不能直接混用测试预期。规模不只有n=|S|，还包括键的位长ℓ、机器字长w及空间预算S_words。静态结构只在构造后查询，动态结构还要支持插入与删除。

在word-RAM里，哪些字操作视为单位成本需要声明，且一个字必须足以寻址相关内存。在cell-probe模型里，只统计访问多少个w位存储单元，单元外计算免费。这比按每条CPU指令计费更宽松，所以相应下界需要非常具体的空间与字长条件。

Pătraşcu与Thorup给出了静态整数前驱的时间空间权衡。本文引用其结果及模型，不重述或自称证明全部分段公式；尤其不能从“前驱有下界”推出对所有整数结构都有Ω(log n)查询下界。

一个直接边界是全宇宙查表：为每个x∈[0,U)保存前驱答案，构造后查询一次索引即可返回，代价是O(U)个表项及相应构造成本。限制接近线性于n的空间时，这个方案通常不再合法。20篇的位图同样靠宇宙范围换取操作便利，不能忽略U。

静态查询下界可以约束同模型、同空间预算的动态结构在构造完后的查询，但它不会自动给出动态更新下界。一个更新昂贵而查询便宜的结构，可能恰好处于另一种时间空间取舍中。

单遍状态能区分多少集合

考虑只插入的单遍数据流，键来自大小为U的已知宇宙。算法确定性地处理输入，结束时必须精确输出不同键的数量；所有随输入变化、可影响后续行为的内部状态都计入内存，不能额外保存一份免费的输入历史。

取所有大小恰为⌊U/2⌋的子集，每个子集按固定顺序作为前缀输入。假设两个不同子集A、B使算法落入同一内部状态。因为大小相同且集合不同，A∖B非空。

现在给两个执行追加完全相同的后缀：宇宙中所有不属于A的元素。A分支最终见过整个宇宙，精确答案为U；B分支仍缺少A∖B，答案小于U。两个执行拥有相同状态、相同后缀和相同总长度，确定性算法却必须给出不同答案，矛盾。

因此这些前缀必须有不同状态。若内存至多s位，状态数至多2^s，于是

s≥log⁡2(U⌊U/2⌋)≥U−log⁡2(U+1)=Ω(U).s\ge\log_2\binom{U}{\lfloor U/2\rfloor}\ge U-\log_2(U+1)=\Omega(U).

第二个不等式来自二项式系数之和为2^U、共U+1项，而中间项最大。固定前缀大小还保证两个输入的位置与最终长度相同；提前知道总长度也不能消除这个区分需求。

这是确定性、精确、单遍不同元素计数的空间下界，不是所有流式统计都需要Ω(U)位。33篇允许误差、采用随机哈希，而且查询接口也不同，不在这个证明的全部条件内。若流允许多遍、额外外存或受限输入，还要重新分析可区分状态，不能省略模型变化。

本篇只给数学证明和模型对照，没有新增教学程序，也没有声称运行实验验证了这些一般下界。有限枚举最多核对小U的计数，不能代替对任意U的状态区分论证。

怎样阅读一个实验中的更快结果

如果整数排序比比较排序快，先看它是否利用了受限值域和字操作。若前驱结构查询只有一次数组访问，先看它是否分配了整个宇宙的表。若流式摘要内存很小，先看它允许哪种误差、能否回答所有需要的查询。

实验中的规模范围、硬件和解释器不会被一个渐近下界自动吸收。下界可以排除模型内的某类一般算法，却通常不告诉两个具体实现在哪个n上发生交叉。38篇将把这类模型判断与实际测量分开记录。

练习

  1. n=4时计算⌈log₂(4!)⌉。构造一个输入承诺，使算法无需分辨24种排列，并说明原下界的哪条输入前提改变了。
  2. 对宇宙大小U、集合大小n，比较全宇宙前驱表与比较搜索树的空间和查询模型。若只允许O(n)个机器字，什么时候不能再使用O(U)表来反驳前驱下界？

参考资料