计算机算法设计与分析 Chapter2 Sorting算法与算法的分析技术.ppt

1比较排序算法与图中的判定树是一致的 2任一比较排序算法对某一确定n值都与一棵判定树相对应 3判定树的全部外部结点对应于所有不同的排序结果例如n = 3时abc的六种不同结果都应包含在判定树的外部结点中 4判定树的结点要么有两个子结点,要么没有子节点 从DT的根到一个叶结点的路长即某条路上的内部结点数也是算法运行所需要的比较次数判定树DT的最长路长即为算法在最坏情形下的比较次数平均路长从根到所有叶