2.3.21

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

解答

首先引入命题 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 \\
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

上一题 下一题