第5章-5 分治 算法设计基本方法.ppt

南京信息工程大学计算机与软件学院 下周二下午交作业1）简述回溯法的基本思想和主要步骤。2）比较回溯法与穷举法的异同。3）简述分支限界法的基本思想和主要步骤。明日3、4节BN604上机 第5-5 分治算法 闫雷鸣 算法总体思想 将要求解的较大规模的问题分割成k个更小规模的子问题。 分治法的适用条件 分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决； 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 解2 分治法：参看教材P112 n≤2，一次比较，得到最重与最轻 n2： 1）金块平均分为A、B两袋； 2）递归，分别找出A、B中的最重与最轻的金块，设为HA、LA、HB、LB 3）比较HA与HB，得到最重的，比较LA与LB，得到最轻的 Example: Find 9 3 5 7 8 9 12 15 Example: Find 9 3 5 7 8 9 12 15 Example: Find 9 3 5 7 8 9 12 15 Example: Find 9 3 5 7 8 9 12 15 计算时间复杂度 课堂练习 试写出二分有哪些信誉好的足球投注网站的递归伪代码或C语言代码 小结 分治法divide-and-conquer 基本步骤： ① 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题。 ② 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题。 ③ 合并：将各个子问题的解合并为原问题的解。 小结 适用条件 ① 该问题的规模缩小到一定的程度就可容易解决。 ② 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。 ③ 利用该问题分解出的子问题的解可以合并为该问题的解。 ④ 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。 递归二分有哪些信誉好的足球投注网站算法： templateclass Type int BinSearch(Type a[], const Type x, int l, int r) { if (l r) return 0; else { int m = (l+r)/2; if (x == a[m]) return m; else if (x a[m]) return BinSearch(a, x, l, m-1); else return BinSearch(a, x, m+1 , l); } return -1; } 算法复杂度分析： 通过证明可得： n=1 n=2 5.5.4 例2 合并排序 基本思想：将待排序元素分成大小大致相同的2个子集合，分别对2个子集合进行排序，最终将排好序的子集合合并成为所要求的排好序的集合。 void MergeSort(Type a[], int left, int right) { if (leftright) {//至少有2个元素 int i=(left+right)/2; //取中点 mergeSort(a, left, i); mergeSort(a, i+1, right); merge(a, b, left, i, right); //合并到数组b copy(a, b, left, right); //复制回数组a } } 复杂度分析 T(n)=O(nlogn) 渐进意义下的最优算法 合并排序 算法mergeSort的递归过程可以消去。 初始序列 [49] [38] [65] [97] [76] [13] [27] [38 49] [65 97] [13 76] [27] 第一步 第二步 [38 49 65 97] [13 27 76] 第三步 [13 27 38 49 65 76 97] 合并排序 最坏时间复杂度：O(nlogn) 平均时间复杂度：O(nlogn) 辅助空间：O(n) 在快速排序中，记录的比较和交换是从两端向中间 进行的，关键字较大的记录一次就能交换到后面单 元，关键字较小的记录一次就能交换到前面单元， 记录每次移动的距离较大，因而总的比较和移动次 数较少