2.2.13平均情况的下限。请证明任意基于比较的排序算法的预期比较次数至少为~NlgN(假设输入元素的所有排列的出现概率是均等的)。提示：比较次数至少是比较树的外部路径的长度(根结点到所有叶子结点的路径长度之和)，当树平衡时该值最小。
答：
1)平均比较次数=总的比较次数/排列数
2)N个输入元素，排列数有N!个。
3)一棵二叉比较树的叶子结点个数为N!，当树平衡时树高h=lgN!，总的比较次数为N!lgN!
代入得:N!lgN!/N!=lgN!~NlgN。
2.2.13平均情况的下限。请证明任意基于比较的排序算法的预期比较次数至少为~NlgN(假设输入元素的所有排列的出现概率是均等的)。提示：比较次数至少是比较树的外部路径的长度(根结点到所有叶子结点的路径长度之和)，当树平衡时该值最小。
答：
1)平均比较次数=总的比较次数/排列数
2)N个输入元素，排列数有N!个。
3)一棵二叉比较树的叶子结点个数为N!，当树平衡时树高h=lgN!，总的比较次数为N!lgN!
代入得:N!lgN!/N!=lgN!~NlgN。