算法-分治法课件.pptVIP

2025/2/4分治法第4章分治法4.1概述4.2排序问题中的分治法4.3组合问题中的分治法4.4几何问题中的分治法分治法是最著名的算法设计技术。1/56

2025/2/4分治法4.1概述4.1.1分治法的设计思想4.1.2数字旋转方阵2/56

2025/2/4分治法将一个难以直接解决的大问题，划分成一些规模较小的子问题，分别求解各个子问题，再合并子问题的解得到原问题的解。4.1.1分治法的设计思想如果子问题的规模仍然不够小，可继续分解下去。3/56

2025/2/4分治法分治法的求解过程：分-治-合（1）划分：把规模为n的原问题划分为k个规模较小的子问题，并尽量使这k个子问题的规模大致相同。（2）求解子问题：各子问题的解法与原问题的解法通常是相同的，可以用递归的方法求解各个子问题。（3）合并：把各个子问题的解合并起来，分治算法的有效性很大程度上依赖于合并的实现。4/56

2025/2/4分治法2.独立子问题：各子问题之间相互独立。1.平衡子问题：最好使子问题的规模大致相同。启发式规则：5/56

2025/2/4分治法子问题1的规模是n/2子问题1的解子问题2的解子问题2的规模是n/2原问题的解原问题的规模是n分治法的典型情况6/56

2025/2/4分治法例：计算an，应用分治技术得到如下计算方法：3432328131319313193333分解问题求解每个子问题合并子问题的解不是所有的分治法都比简单的蛮力法更有效。分析时间性能??éù?íì′==1122naanaannn如果如果7/56

2025/2/4分治法4.1.2数字旋转方阵问题：输出N?N(1?N?10)数字旋转方阵。2019181716213231301522333629142334352813242526271278910116?6的旋转方阵8/56

2025/2/4分治法4.2排序问题中的分治法4.2.1归并排序4.2.2快速排序9

2025/2/4分治法4.3.1归并排序二路归并排序的分治策略是：（1）划分：将待排序序列r1,r2,…,rn划分为两个长度相等的子序列r1,…,rn/2和rn/2＋1,…,rn；（2）求解子问题：分别对这两个子序列进行排序，得到两个有序子序列；（3）合并：将这两个有序子序列合并成一个有序序列。10/56

2025/2/4分治法r1……rn/2rn/2＋1……rn划分r‘1……r’n/2r’n/2＋1……r’n递归处理r1……rn/2rn/2＋1……rn合并解举例：8326715411/56

2025/2/4分治法算法4.3——归并排序voidMergeSort(intr[],ints,intt){intm,r1[1000];if(s==t)return;else{m=(s+t)/2;Mergesort(r,s,m);//归并排序前半个子序列Mergesort(r,m+1,t);//归并排序后半个子序列Merge(r,r1,s,m,t);//合并两个已排序的子序列for(inti=s;i=t;i++)//将有序序列传回数组r中r[i]=r1[i];}}C++描述12/56

2025/2/4分治法二路归并排序的合并步的时间复杂性为O(n)，所以，二路归并排序算法存在如下递推式：可得二路归并排序的时间代价是O(nlog2n)。二路归并排序在合并过程中需要与原始记录序列同样数量的存储空间，因此其空间复杂性为O(n)。?íì+==1)2(211)(nnnTnnT13/56

2025/2/4分治法算法4.4——合并有序子序列voidMerge(intr[],intr1[