先修：04 归纳证明；07 乘法计数与排列；08 鸽巢原理
桌上有A到H八张卡片。朋友选定其中一张，保证没有选桌外的卡，也不会中途更换。你只能问回答为“是”或“否”的问题，要确定是哪一张。
问“是A吗”，如果答是，一下就排除了七张；如果答否，却还剩七张。问“在A、B、C、D里吗”，无论怎么回答，都只剩四张。
所以，标题不能简单回答成“一个问题最多排除一半”。某个回答可以排除很多，另一个回答却可能没帮上多少忙。我们真正想知道的是：怎样安排问题，才能保证无论选了哪张卡，都在有限次回答后认出它？
第07章数过二元选择，第08章证明过编号不足时必有碰撞。现在把它们接起来：如果回答路径太少，不同目标就会走到同一个结果，正确识别便无从谈起。
好问题要照顾较难的那个回答
一个是非问题把当前候选分成两组：会回答是的，以及会回答否的。问题可以很复杂，但每张候选必须恰好属于其中一组，回答也必须真实。
如果当前有m张卡，两组数量相加就是m。因此至少有一组包含不少于⌈m/2⌉张。符号⌈x⌉表示向上取整，也就是不小于x的最小整数，例如⌈7/2⌉＝4。
只要那一组确实可能被选中，这次回答后就可能还剩这么多候选。想优化最坏情形，应尽量让两组大小接近，而不能只盯着一个特别幸运的回答。
图1：这里比较的是两个回答中较难的一个，没有假设每张卡出现的机会相同，也没有计算平均次数。
八张卡先分四与四，再把留下的四张分二与二，最后分一与一。三次回答足够。最后只剩一张时可以直接报出它，因为一开始已经保证目标在这八张里。
但“三次够用”还没有证明“两次一定不行”。也许有一种特别巧的问法，绕开了我们刚才的均分？要回答它，需要把所有问法放到同一种表示里。
把整套问法画成一棵树
把第一个问题放在最上方，称作根。它向下伸出“是”和“否”两条分支，各自连接下一步的问题。问题可以根据之前的回答改变，不必预先问同一套固定问题。
不再提问、直接报出卡片的地方，称作叶子。一次游戏从根出发，沿真实回答选择分支，最后到达一个叶子。路径经过几个问题，就用了几次回答；所有路径中最大的次数，称作这棵决策树的深度。
图2：左分支表示是，右分支表示否。第二问、第三问会随前面的回答改变，但每个问题仍只有两个出口。
现在证明：深度不超过k的二叉决策树，叶子至多有2ᵏ个。这里k是非负整数，“二叉”只要求每个问题至多有两个分支，不要求两边一样大。
k＝0时不能再问，整棵树只有一个叶子，正好是2⁰＝1。假设深度不超过k－1的树至多有2ᵏ⁻¹个叶子。深度不超过k的树若直接结束，只有一个叶子；若先问一个问题，左右两棵子树的深度都不超过k－1，各自至多有2ᵏ⁻¹个叶子，合起来至多是2ᵏ。起点和传递步骤都成立，证明完成。
这个证明也照顾了提前结束的路径。不能把长度为0、1、2……k的所有回答串都相加，声称可以识别2⁰＋2¹＋…＋2ᵏ种目标：一条路径如果已经结束，就不会再从那个叶子继续提问；这些长度不同的终点不能任意同时放进同一棵树。
从回答容量得到一个下界
如果两张不同卡片到达同一个叶子，我们就会给它们报出同一个身份，至少错一次。因此，要保证认出n张候选中的任意一张（n≥1），树必须至少有n个叶子。这正是上一章“不能让不同对象挤进同一个编号”的要求。
假设最多允许k次是非回答，两边夹起来便得到：
n ≤ 叶子数 ≤ 2ᵏ。
所以必须有2ᵏ≥n。八张卡时，两次回答至多提供2²＝4个叶子，容不下八种身份；三次则有2³＝8个位置，刚才的策略确实用满了它们。
“2的多少次方等于n？”这个指数叫以2为底的对数，记作log₂n。因为2³＝8，所以log₂8＝3；因为2¹⁰＝1024，所以log₂1024＝10。n不是2的整数次方时，对数可以不是整数，而问题次数只能是整数。刚才的必要条件于是写成：
k ≥ ⌈log₂n⌉。
它叫作下界：任何满足这些规则、对所有候选都正确的提问策略，总有某个目标需要至少这么多次回答。它没有说每个目标都一样难，也没有假设目标如何随机产生。
一百万张卡的数字很具体：2¹⁹＝524,288，2²⁰＝1,048,576。十九次回答的容量不足，二十次才可能够用。
在允许询问任意候选子集的卡片游戏里，这个下界能够达到。给n张卡分别分配一个不同的k位二进制编号，其中k＝⌈log₂n⌉。第07章已经证明，这样的编号有2ᵏ个，数量够用。依次问“目标编号的第i位是1吗”，k次回答就完整恢复编号，进而确定卡片。多出来的编号不分给任何卡，不会造成歧义。
于是这里的最少最坏次数恰好是⌈log₂n⌉。候选数量翻倍，所需次数只增加一次，这就是对数增长的一个具体含义。不过，这个游戏只收费于回答次数，没有计算把巨大候选子集写出来、检查卡片是否属于它的成本。
排序也在区分可能
换成四条记录A、B、C、D。每条都有一个用于排序的键，键彼此不同，能够比较大小。我们看不见键的内部表示，只能通过“A的键小于B的键吗”这样的二元比较取得顺序信息，并据此移动记录。
这是比较排序模型。先固定一个确定的算法：同样的比较结果历史，会决定同样的下一步。即使算法内部移动过记录，我们也始终按记录原来的身份追踪它们。
四条记录共有4!＝24种可能的相对次序。比如A＜B＜C＜D时，正确输出是ABCD；B＜A＜C＜D时，则必须输出BACD。这里数的是记录身份的输出顺序，而不是把一组固定数值排序后总会得到的那串相同数字。
任意一种完整相对次序，都要求一个唯一的身份排列作为正确结果。如果两种不同次序走到同一个叶子，算法就会执行同一种输出排列，无法同时正确。因此排序决策树至少要有24个叶子。
图3：每个小格代表一个可用叶子位置。四次比较的容量小于24，因此不能保证排完；五层容量足够，不等于任意五次比较都能完成排序。
因为2⁴＝16＜24≤32＝2⁵，任何这类算法总有一种输入需要至少五次比较。推广到n条互异记录，需要n!个不同叶子，便得到：
最坏比较次数 ≥ ⌈log₂(n!)⌉。
CMU 15-451讲义第5.2节用同样的比较模型，把排序看作辨认正确输出排列的问题。重要之处在于，证明没有指定某一种排序程序；只要程序的信息来自这些比较，就都在这条下界的范围内。
阶乘取对数有多大
这个式子也能解释排序下界为何比查找大得多。先让n是一个不小于4的偶数。n!中的每个因子都不超过n，所以n!≤nⁿ；后半段的n/2个因子都至少为n/2，其余因子至少为1，所以：
(n/2)ⁿᐟ² ≤ n! ≤ nⁿ。
对数保持大小关系；乘积的对数变成相加，来自指数规律2ᵃ×2ᵇ＝2ᵃ⁺ᵇ。于是：
(n/2)×log₂(n/2) ≤ log₂(n!) ≤ n×log₂n。
又因为log₂(n/2)＝log₂n－1，而n≥4时log₂n≥2，左边至少是(n/4)×log₂n。这样，log₂(n!)被夹在n×log₂n的四分之一与一倍之间。奇数规模也可以用相邻两个偶数的阶乘夹住，增长方式不变。
这就是“n log n量级”在这里的意思：随着规模增大，这条计数下界本身与n乘以log₂n相比，只相差固定倍数范围。它不是说任意排序算法都恰好做n log₂n次比较，更没有给出所有算法的实际耗时。某个算法可能多做很多工作；怎样安排步骤接近这条界限，是下一章的问题。
边界换了，结论也要重查
首先，一个操作若能返回“小于、等于、大于”三种结果，就不是本章的一次二元回答。一般三叉树深度k至多有3ᵏ个叶子，不能直接套2ᵏ。互异键之间的大小比较可以排除相等分支；查询值与某条记录比较时却未必能排除。必须先数真实可能的出口，不能把一整轮三路判断自动算作一个比特。
其次，若任务只要求回答“在不在”，多个不同目标可以共享一个“在”的输出，不再必须各占一个叶子。因而不能仅凭候选有n个，就把前面的n叶论证原样搬来。这不表示成员查询没有下界，只表示还需要符合它的任务和操作规则的证明。
再次，比较模型没有禁止模型之外的办法。MIT 6.006第4讲在讲过比较决策树后转向直接寻址与散列：若允许利用键的内部表示计算位置，获得信息的方式已经改变。第08章的分桶查找并不需要“打破”这棵树；它使用了额外操作，仍要处理各自的正确性与成本。
二分为什么接近这里的增长速度
在排好序、能够按下标有效读取中间项的数组里，一次大小判断可以排除连续一段候选。Princeton《Sorting and Searching》从猜数字到有序数组说明了这种二分思路。它让对数增长成为实际算法里的常见现象。
但要分清数的是什么。采用“读靠左中点，相等就返回，否则排除中点”的查找写法，允许目标不存在。当前有m项时，未找到后的候选至多剩⌊m/2⌋项；这里⌊x⌋表示向下取整。目标比最大项还大时，每次都走到右侧较大的半段，r轮后恰剩⌊n/2ʳ⌋项。要缩到0，需2ʳ＞n，因此最坏需要⌊log₂n⌋＋1轮，n＞0。一百万项是20轮，1024项是11轮；后者与保证命中的卡片游戏所需10次回答不同。
这数的是查看中间项的轮数，并不是二元判断数、CPU指令数或磁盘读取次数。数据还必须按相同规则有序；若先排序，排序费用也要另算。普通链表即使比较不多，走到中点仍可能费时。这些条件决定对数级的提问节省能否变成真正的时间收益。
下次听见“再优化一下，应该还能少很多”，可以先把任务写成三个具体问题：哪些情况必须区分，一次操作能给出几个结果，哪些成本还没有计入。计数给出的下界能帮助我们判断，应该继续改进步骤，还是需要换一种可用信息或数据组织方式。
顺手试一下
题目1：十三张卡的第一问
目标保证在十三张卡里，可以询问任意候选子集。最少多少次是非回答能够保证认出目标？若第一问固定为“是A吗”，否之后再采用最优策略，最坏总共要问几次？
**提示：**先比较十三与相邻的2的整数次方，再计算第一问答否后的剩余规模。
**参考答案：**2³＝8＜13≤16＝2⁴，所以至少四次；给十三张卡分配不同四位编号即可达到。也可以先分六与七，之后继续均分，剩余最多依次为7、4、2、1。若第一问只问A，答否后还有十二张，至少再需要⌈log₂12⌉＝4次，也能够做到，因此最坏总共五次。容量下界约束所有策略，但并不保证每种问法都最优。
题目2：要辨认的究竟是什么
五条键互异的记录做比较排序，能否保证六次比较完成？若改成四条记录，只判断A的键是不是最小，有人仍以4!＝24种次序为由，声称至少五次比较。他的证明哪里失效？
**提示：**完整排序需要区分哪些输出？判断A是否最小，又需要区分哪些？
**参考答案：**5!＝120，而2⁶＝64＜120，故完整排序不能保证六次完成，最坏至少七次。但计数本身没有证明七次一定足够。第二问只输出是或否，多种完整次序可以得到同一个正确结果，并不需要24个叶子。分别比较A与B、C、D，任一次发现比A更小的键就回答否；三次都没有则回答是，至多三次就够。原证明把任务不要求区分的次序也当成了必须分别输出的结果。
来源与延伸阅读
- CMU 15-451，Lecture 5，Comparison-based Lower Bounds for Sorting，印刷页24—25：比较模型、n!种输出排列与最坏情形下界
- MIT 6.006，Lecture 4，Hashing，第1—2页：二元比较决策树，以及超出比较模型的直接寻址
- Princeton，Introduction to Programming，4.2 Sorting and Searching：二十问、有序数组与二分查找的前提
作者：Jiancheng Wang · 数学之美（独立原创）