2.3.21 #
解答 #
首先引入命题 I 的结论，对于互不相同的主键值，基于比较的排序算法的下界等于所形成的比较树的高度，即：
$$ h \ge \log_2{N!} $$
那么我们题目即可转化为求证
$$ h \ge \log_2 (\frac{N!}{f_1!f_2!\cdots f_k!}) \ge \log_2 N! $$
这里的 $f_i$ 为某个主键值出现的频率，即某个主键值出现的次数，因此 $f_i\ge 1$ 。
根据题目给出的条件，如果主键互不重复，此时 $k=N$，且 $f_1=f_2=\cdots=f_k=1$ 。
那么 $f_1!f_2!\cdots f_k!=1$ ，待证式子即为命题 I 的结论。
那么当主键有重复时，此时 $k < N$，为使 $f_1+f_2+ \cdots + f_k=N$ ，至少存在一个 $f_m \ge 2$。
故此时：
$$ f_1!f_2!\cdots f_k! >1\Rightarrow \frac{N!}{f_1!f_2!\cdots f_k!}<N! \Rightarrow \newline h \ge \log_2 (\frac{N!}{f_1!f_2!\cdots f_k!}) \ge \log_2 N! \ \blacksquare $$
得证。