3.2.24

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

解答

根据命题 D (英文版 P404,中文版 P255),一次插入所需的比较次数平均为 $ 1.39\lg N$。
(我们这里要求和,因此可以直接使用平均值进行计算)
于是构造一棵二叉查找树所需的比较次数为:
$$
1.39C= 1.39\sum_{i=0}^N \lg i=1.39 \times(\lg 1 + \lg2+\cdots+\lg N)
$$
根据对数恒等式,有:
$$
C=\lg 1 + \lg2+\cdots+\lg N=\lg(1\times2\times3\times\cdots\times N)=\lg(N!)
$$
于是有 $ 1.39C=1.39\lg(N!) > \lg(N!)$ ,得证。

上一题 下一题