algorithm - 排序算法边界证明

Question

基于这张幻灯片： http: //oi48.tinypic.com/27xmg47.jpg

Q1> 为什么N!不同的排序=>至少N!离开？

Q2> 为什么#leaves >= N!？

2^h >= #leaves 的原因是 2^h 表示完全二叉树中的叶子数，而#leave 大部分时间来自不完全二叉树。

Answer 1

有N!不同的顺序。该算法必须准确地确定存在哪种排序，因此其决策树必须至少有N!叶子。否则，它将无法区分所有可能的排序。