南开大学算法导论第五章课件.pdf

第五章 分治策略 苏 明 1 分治策略 “分而治之” 把一个问题分解成几个部分 递归解决规模比较小的类似问题 把子问题的解合成完整的解 2 分治策略 经常使用的办法： 把一个规模为n的问题分解成两个规模½n 的问题； 分别递归解决两个部分的问题； 在线性时间内把这两个部分问题的解合 成一个完整的解。 3 归并排序算法 问题：给定n个元素，按照递增的顺序对 其进行排序。 排序应用场景： 直接应用： 间接应用： 目录文件排序； 区间调度； 电话簿排序； 最小生成树问题； Google上输出按照 PageRank排序； 数据压缩； 4 归并排序 归并排序 Divide array into two halves. Recursively sort each half. Merge two halves to make sorted whole. Jon von Neumann (1945) A L G O R I T H M S A L G O R I T H M S divide O(1) A G L O R H I M S T sort 2T(n/2) A G H I L M O R S T merge O(n) 5 归并排序 合并：把两个排好序的部分合成一个完整 的排序 效率分析：采用一个临时数组；需要O(n) 次比较 A G L O R H I M S T A G H I 6 归并排序 对于归并排序算法，设T(n)表示该算法 在规模为n的输入实例上最坏的运行 （比较）时间。 开始假设n是2的整数次幂 可以得到递归公式如下： 7 递推关系 命题5.1 对某个常数c, 2T (n / 2) + cn, n 2 ⎧ T (n) ≤ ⎨ c, n 2 ⎩ 或者 ⎧ 0