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$$

得证。

另请参阅 #

lower bounds of sorting-The University of Maryland