2.2.13

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

假设对三个数进行排序,
这三个数是:35,10,17
三个数排序的决策树如下,
结点代表比较对应位置上的数。

对于 35,10,17 来说,路径遵循右、左、左,最后得到的结果就是 2 3 1(10,17,35)。
我们可以发现决策树上的每一个叶子节点都代表一种排列顺序,对于 N 个数,叶子节点就有 $ N! $ 个
根据二叉树的性质,高度为 $ h $ 的二叉树最多有 $ 2^h $ 个叶子节点
那么,对于 $ N $ 个数,决策树的高度 $ h $ 的最小值可以通过下面这个式子得出来
$ 2^h >= n! $
$ h \ge log(n!) $
因此可以得到决策树高度 $ h $ 的最小值是 $ log(n!) $

接下来我们来计算平均路径长度
我们令函数 $ H(k) $ 代表有 $ k $ 个叶子节点的平衡决策树的所有路径长度之和
上例中 $ H(6) = 2 + 2 + 3 + 3 + 3 + 3 = 16 $
由于平衡决策树的性质,$ H(k) = 2H(k / 2) + k $
(加上 $ k $ 的原因:左右子树的高度比整个树的高度小 $ 1 $,因此每条路径的长度都必须加 $ 1 $,总共多加了 $ k $ 次)
因此 $ H(k) = klogk $
现在令 $ k = n! $
$ H(n!) = n!log(n!) $
由于每次排序时我们只经过某一条路径(上例中我们只经过了右、左、左这条路径)
而且每种路径的出现概率相等
因此平均比较次数应该为 $ H(n!) / n! = log(n!) = nlog(n) $
证明完毕

另请参阅

排序算法的下界-Data Selection. Lower bound for sorting-PDF

上一题 下一题