3.2.24 #

解答 #

根据命题 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!)$ ，得证。