为何比较排序对应二叉决策树的叶子节点数为n!？（与排序下界相关）

我们将树的外部路径长度定义为从根节点到每个叶子节点的路径长度之和。基于比较的排序算法的平均时间复杂度等于其对应二叉决策树（BDT）的外部路径长度除以叶子节点数，该节点数为n!。请问为何该二叉决策树的叶子节点数是n!？此问题与排序的平均情况下界相关。

这事儿得从二叉决策树的本质说起——它的每一个叶子节点，对应着一组输入数据的唯一排序结果。

咱们想啊，当你要排序n个不同的元素时，所有可能的排列组合总共有多少种？没错，就是n的阶乘，也就是n!。因为第一个元素有n种选择，第二个有n-1种，以此类推，乘起来就是n!种不同的排列。

而基于比较的排序算法，每一次比较都是二叉决策树的一个内部节点：左分支代表“小于/等于”的情况，右分支代表“大于”的情况（或者反过来，取决于算法的实现）。每一条从根到叶子的路径，就对应着算法完成一次排序的完整决策过程，最终到达的叶子节点，就是这次排序得到的最终有序排列。

这里有个关键：对于一个正确的排序算法，它必须能处理所有可能的输入排列，也就是说，每一种可能的排列都得对应二叉决策树里的一个叶子节点。不然的话，就存在某种排列算法处理不了，那这个算法显然是有问题的。

另外，从排序下界分析的角度来说，我们只需要考虑“最小的必要二叉决策树”——也就是每个叶子节点对应唯一的排列结果，不会有重复的情况。这时候叶子节点的数量就正好等于所有可能的排列数，也就是n!。

所以总结下来：因为n个元素的所有可能排列是n!种，而二叉决策树的每个叶子对应一种唯一的排序结果，所以叶子节点数就是n!。这也是为什么我们能通过二叉决策树的外部路径长度来推导排序算法的平均时间复杂度下界——毕竟你得覆盖所有可能的排列情况嘛。

内容的提问来源于stack exchange，提问作者D-PUNK-R