你会如何使用决策树来证明搜索n个元素的排序列表与比较基于模型有下界欧米茄（log n）的？
如果你必须使用一个决策树...
对于给定长度n，一个基于比较的算法的行为可以被表示为一个决策树，其中每个叶是你通过的路径，该叶表示的比较和结果的序列之后得到的结果。
你必须证明，在决策树具有n个叶子和3分支系数，叶最长路径必须至少有小区（log_3（n））的内部节点。
你会感应证明这一点，证明它是如此的n个{1,2,3}，这意味着它是所有更大的ñ真实的，因为如果一个节点的子树有n个叶，那么它的一个孩子需要有至少n / 3的叶子。
请注意，下界搜索问题必须至少为寻找在排序后的数组中的条目的问题一样大，假设该条目已经存在。为了解决这个新的问题，代表你在你的树中的节点的相关信息，具体的节点是一组在你的价值可能在于索引。最初，您的值可以对应于任何索引，所以你的根将是{0,1，...，N}。
每当你做一个比较，因为数组排序有三种可能的结果：要么你正在寻找的价值比你已经将它比作一个更大的，或者它的值小于或等于它，所以你已经一分为三的可能的指标集。在当前节点代表一个单集，和比较的数量相当于树的高度你的算法解决了这个问题。
其将树到最小高度的n个单叶的树是顺序的log（n），并且使得为任何算法下界。