算法-分治法.ppt

*。*/56**/56*分治法将一个难以直接解决的大问题,划分成一些规模较小的子问题,分别求解各个子问题,再合并子问题的解得到原问题的解。,可继续分解下去。*/56*分治法分治法的求解过程:分-治-合(1)划分:把规模为n的原问题划分为k个规模较小的子问题,并尽量使这k个子问题的规模大致相同。(2)求解子问题:各子问题的解法与原问题的解法通常是相同的,可以用递归的方法求解各个子问题。(3)合并:把各个子问题的解合并起来,分治算法的有效性很大程度上依赖于合并的实现。*/56*:各子问题之间相互独立。:最好使子问题的规模大致相同。启发式规则:*/56*分治法子问题1的规模是n/2子问题1的解子问题2的解子问题2的规模是n/2原问题的解原问题的规模是n分治法的典型情况*/56*分治法例:计算an,应用分治技术得到如下计算方法:34323281313**********分解问题求解每个子问题合并子问题的解不是所有的分治法都比简单的蛮力法更有效。分析时间性能ëûéùîíì>´==1122naanaannn如果如果*/56*:输出NN(1N10)数字旋转方阵。20191817162132313015223336291423343528132425262712789101166的旋转方阵*/56***:(1)划分:将待排序序列r1,r2,…,rn划分为两个长度相等的子序列r1,…,rn/2和rn/2+1,…,rn;(2)求解子问题:分别对这两个子序列进行排序,得到两个有序子序列;(3)合并:将这两个有序子序列合并成一个有序序列。*/56