决策树模型

形式陈述 ​

确定性决策树的每个内部节点指定一次允许的查询，出边对应可能答案，叶结点标记输出。给定输入后，查询答案唯一决定从根到某个叶的路径；该路径上的节点数是本次查询成本，树的最大深度是最坏查询复杂度。在输入分布 $\mu$ 下，平均查询复杂度是叶深度的期望 ${\mathbb{E}}_{x\sim \mu }[d(x)]$。

对互异键的比较排序公理库比较排序Comparison sorting仅通过元素两两比较确定排列次序的排序模型。，查询“$a_i<a_j$ 吗”只有真假两种答案，可用二叉树公理库二叉树Binary tree每个节点至多有两个有序子节点的根树。表示。算法必须区分 $n!$ 种输入相对次序，因此树至少有 $n!$ 个可达叶。深度为 $d$ 的二叉树至多有 $2^d$ 个叶，从而

$$d\ge \lceil {\log }_2(n!)\rceil =\mathrm{\Omega }(n\log n).$$

若允许相等键并以比较结果 $<,=,>$ 分支，模型是三叉树；下界必须按相应叶数和输入类别重新计算。

直觉 ​

决策树删去赋值、循环和代码语法，只保留算法向输入提出的问题以及答案如何改变后续问题。一个叶代表算法已经收集到足以确定输出的信息；若两个应产生不同输出的输入仍能走到同一叶，算法就不正确。下界因此变成信息区分问题：每次查询最多产生多少分支，最终又必须区分多少种情形。

模型的力量也正是限制。允许任意“答案是否为目标值”的查询，一步就能解决原问题；只允许元素比较，才得到比较排序下界。引用决策树结果时必须同时写出查询集合、答案数和成本单位，不能只报一个树高。

例子与边界 ​

三个互异元素共有 $3!=6$ 种相对次序。深度 $2$ 的二叉树最多有 $4$ 个叶，不足以分别标记六种排序结果，因此某些输入至少需要三次比较。具体算法可以先比较 $a$ 与 $b$，再根据结果选择比较 $b$ 与 $c$ 或 $a$ 与 $c$；路径会因输入而异，但任何正确树的最大深度都不能低于 $3$。

叶数论证给最坏下界，也可结合 Kraft 不等式分析均匀分布下的平均深度。它不证明所有操作模型中的排序都需 $\mathrm{\Omega }(n\log n)$：整数键若允许 word 操作、数组寻址或基数分解，可以使用比较之外的信息并突破该界。

随机算法可看成先随机选择一棵确定性树，或在节点加入随机分支。某棵确定性树的叶数下界不能直接推出其分布的期望下界；通常还需 Yao 极小极大原理，把一个困难输入分布上的确定性平均成本转成随机算法下界。忽略这一步会把确定性结论错误扩大。

推论与应用 ​

决策树统一描述比较排序、选择、成员查询和许多黑盒问题的查询复杂度。它可以用叶数给信息论下界，也可以配合对手法维护尚未区分的输入集合。上界算法则对应一棵具体树，其不同路径揭示自适应查询如何利用早期答案。

该模型并不评价查询之外的计算；若构造下一次查询本身昂贵，真实运行时间还要另算。反过来，证明在计算免费时仍需要许多查询，往往能得到更稳健的访问或比较下界。

参考资料

• Thomas H. Cormen et al., Introduction to Algorithms, 4th ed., MIT Press, 2022, §8.1, lower bounds for sorting.
• Donald E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, 2nd ed., Addison-Wesley, 1998, §5.3.1.