决策树模型

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

模型的力量也正是限制。若允许直接询问目标函数值，一次查询就能完成求值；这类查询的答案集合还可能很大。只允许元素比较，才得到比较排序下界。引用决策树结果时必须同时写出查询集合、答案数和成本单位，不能只报一个树高。

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

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

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

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

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