算法2013s(L5)-线性时间排序.pdf

算法设计与分析 讲授内容：动态规划I 教 师：胡学钢、吴共庆 2013年5月15 日 排序可以做到多快？ 至今为止，我们见过的排序都是 比较排序 : 仅仅 使用比较来比较各项的相对顺序 . • 比如：插入排序,合并排序,快速排序, 堆排序. 我们见过的比较排序的最好的最坏运行时间是O (nlgn). O(nlgn)是不是我们能做到的极限? 决策树 可以帮助我们回答这个问题 . 5/15/2013 算法设计与分析-线性时间排序 2 决策树举例 排序 〈a , a , …, a 〉 1 2 n 每个内部节点标识为 i:j i,j ∈{1, 2,…, n}. •左子树表示当a ≤ a 时的比较序列 . i j •右子树表示当a ≥ a 时的比较序列 . i j 5/15/2013 算法设计与分析-线性时间排序 3 决策树举例 排序 〈a , a , a 〉 1 2 3 = 〈9 , 4 , 6 〉: 每个内部节点标识为i:j ,i,j ∈{1, 2,…, n}. •左子树表示当a ≤a 时的比较序列 . i j •右子树表示当a ≥a 时的比较序列 . i j 5/15/2013 算法设计与分析-线性时间排序 4 决策树举例 排序 〈a , a , a 〉 1 2 3 = 〈9 , 4 , 6 〉: 每个内部节点标识为i:j ,i,j ∈{1, 2,…, n}. •左子树表示当a ≤a 时的比较序列 . i j •右子树表示当a ≥a 时的比较序列 . i j 5/15/2013 算法设计与分析-线性时间排序 5 决策树举例 排序 〈a , a , a 〉 1 2 3 = 〈9 , 4 , 6 〉: 每个内部节点标识为i:j ,i,j ∈{1, 2,…, n}. •左子树表示当a ≤a 时的比较序列 . i j •右子树表示当a ≥a 时的比较序列 . i j 5/15/2013 算法设计与分析-线性时间排序 6 决策树举例 排序 〈a , a , a 〉 1 2 3 = 〈9 , 4 , 6 〉: 每个内部节点标识为i:j ,i,j ∈{1, 2,…, n}. •左子树表示当a ≤a 时的比较序列. i j •右子树表示当a ≥a 时的比较序列. i j 5/15/2013 算法设计与分析-线性时间排序 7 决策树模型 决策树可以模拟任何的