下载文档原格式
分治算法讲解分治算法一：基本概念（分而治之）分治就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
比如：二分查找，归并排序，快速排序，树的遍历等等任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。
问题的规模越小，越容易直接求解，解题所需的计算时间也越少。
例如，对于n个元素的排序问题，当n=1时，不需任何计算。
n=2时，只要作一次比较即可排好序。
n=3时只要作3次比较即可，…。
而当n 较大时，问题就不那么容易处理了。
要想直接解决一个规模较大的问题，有时是相当困难的。
二：基本思想分治设计思想：将一个大的问题，分解成一个个小的，相同类型的问题，然后逐个击破各个小问题，最后将小问题逐步合并，得到最终的解。
（可能会用到递归，大问题里包含小问题，找到规律然后解决）分治基本策略：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n 较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。
三：分治使用情况1) 该问题的规模缩小到一定的程度就可以容易地解决2) 该问题可以分解为相同类型的小问题（前提）3) 利用该问题分解出的子问题的解可以合并为该问题的解；（关键）4) 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子子问题。
第三条特征是关键，能否利用分治法完全取决于问题是否具有第三条特征，如果具备了第一条和第二条特征，而不具备第三条特征，则可以考虑用贪心法或动态规划法。
四：基本步骤（1）划分：把问题的实例划分成子问题（2）求解：若是子问题比较简单，就直接解决，否则递归求解子问题（3）合并：合并子问题的解得到原问题的解课前引导：一：分段函数例如：高中数学中的分段函数也是类似分治思想的体现，如看图求y关于x的表达式。
算法设计与分析典型算法概述▌分治法与贪心法▌拾光工作室分治法分治算法也叫分治策略，把输入分为若干个部分，递归的解每一个问题，最后将这些子问题合并成为一个全局解。
如果子问题较大，可以再次使用分治策略。
由此可以得到分治策略解决的问题特点：1.该问题的规模缩小到一定的程度就可以容易地解决；2.该问题可以分解为若干个规模较小的相同问题;3.分解出的子问题的解可以合并为原问题的解；4.分解出的各个子问题是相互独立的。
分治法的应用——二叉查找设a[i]（1<=i<=n）是一个数组，其中的元素以非降序排列.考虑判断一个元素x是否在数组中的问题。
确定一个j，使得a[j]=x。
如果x在数组中返回j，否则，返回0。
分析该问题符合分治法策略解决问题的特点，可以用分治法解决：如果n=1，直接判断a[n]是否与x相等。
如果n>1,可以把问题分解如下新的问题：选择一个下标q(范围[i,l]中)，比较x与a[q]，则有三种情况：1.x=a[q].得到解。
2.x>a[q].问题范围转换为(l-q,a[q+1], (x)3.x<a[q].问题范围转换为(q-i,a[i], (x)转换的子问题可以继续分解。
二叉查找的递归算法int BinSrch(Type a[],int i,int n,Type x)//a[i..n]是非递减排列且 1<=i<=n;{if(n==i) { if(x==a[i]) return i;else return 0; }else{int mid=(i+n)/2;if(x==a[mid]) return mid;else if(x<a[mid]) return BinSrh(a,i,mid-1,x);else if(x>a[mid]) return BinSrh(a,mid+1,n,x);}}分治法的应用——查找最大值与最小值在n个元素中找出最大值和最小值首先看下简单的查找算法：void MaxMin(Type a[],int n,Type &max,Type &min){max=min =a[0];for(int i=1;i<n;i++){ if(a[i]>max) max=a[i];if(a[i]<min) min=a[i];}}算法的时间复杂度体现在比较的次数上，当a[n]中的元素是多项式，矢量及非常大的数时或字符串，元素的比较代价就比其他操作代价高的很。
算法设计技巧与分析参考答案第1章算法分析基本概念1.1(a)6 (b)5 (c)6 (d)61.4算法执行了7+6+5+4+3+2+1=28次比较1.5(a)算法MODSELECTIONSORT执行的元素赋值的最少次数是0,元素已按非降序排列的时候达到最小值。
(b) 算法MODSELECTIONSORT执行的元素赋值的最多次数是3(1)2n n ,元素已按非升序排列的时候达到最小值。
1.7由上图可以看到执行的比较次数为1+1+2+2+2+6+2=16次。
1.11由上图可以得出比较次数为5+6+6+9=26次。
1.13FTF,TTT,FTF,TFF,FTF 1.16(a) 执行该算法，元素比较的最少次数是n-1。
元素已按非降序排列时候达到最小值。
(b) 执行该算法，元素比较的最多次数是(1)2n n -。
元素已按非升序排列时候达到最大值。
(c) 执行该算法，元素赋值的最少次数是0。
元素已按非降序排列时候达到最小值。
(d) 执行该算法，元素赋值的最多次数是3(1)2n n -。
元素已按非升序排列时候达到最大值。
(e)n 用O 符号和Ω符号表示算法BUBBLESORT 的运行时间：2()t O n =，()t n =Ω(f)不可以用Θ符号来表示算法的运行时间：Θ是用来表示算法的精确阶的，而本算法运行时间由线性到平方排列，因此不能用这一符号表示。
1.27不能用关系来比较2n 和2100n 增长的阶。
∵221lim0100100n n n →∞=≠ 2n ∴不是2(100)o n 的，即不能用关系来比较2n 和2100n 增长的阶。
1.32(a)当n 为2的幂时，第六步执行的最大次数是：12,2k k n j -==时，11[log ]log n ni i k n n n ====∑∑(b)由(a)可以得到：当每一次循环j 都为2的幂时，第六步执行的次数最大，则当33,22k kmn j ===（其中32k 取整）时，11[log(31)]log(1)n nkii i m n n ===-=-∑∑(c)用O 符号表示的算法的时间复杂性是(log )O n n 已证明n=2k 的情况，下面证明n=2k +1的情况：因为有⎥⎦⎥⎢⎣⎢+=⎥⎦⎥⎢⎣⎢21222k k所以n=2k +1时，第六步执行的最大次数仍是n log n 。
算法分析——分治法分治算法⼩组的汇报内容：⼀、分治算法的基本概念 (2)⼆、分治算法的基本思想及策略 (2)三、分治法适⽤的情况 (3)四、分治法的基本步骤 (3)五、分治法的复杂性分析 (4)六、快速傅⾥叶变换 (5)七、可使⽤分治法求解的⼀些经典问题 (9)⼋、依据分治法设计程序时的思维过程 (9)九、分治法与其它常见算法的⽐较 (9)⼩组的分⼯情况：彭勇讲前五个部分，天西⼭讲第六个部分，胡化腾讲最后三个部分，吕璐负责汇报的资料收集，⼩组分⼯以及最后的资料整理。
三、分治法适⽤的情况分治法所能解决的问题⼀般具有以下⼏个特征：1) 该问题的规模缩⼩到⼀定的程度就可以容易地解决2) 该问题可以分解为若⼲个规模较⼩的相同问题，即该问题具有最优⼦结构性质。
3) 利⽤该问题分解出的⼦问题的解可以合并为该问题的解；4) 该问题所分解出的各个⼦问题是相互独⽴的，即⼦问题之间不包含公共的⼦⼦问题。
第⼀条特征是绝⼤多数问题都可以满⾜的，因为问题的计算复杂性⼀般是随着问题规模的增加⽽增加；第⼆条特征是应⽤分治法的前提它也是⼤多数问题可以满⾜的，此特征反映了递归思想的应⽤；、第三条特征是关键，能否利⽤分治法完全取决于问题是否具有第三条特征，如果具备了第⼀条和第⼆条特征，⽽不具备第三条特征，则可以考虑⽤贪⼼法或动态规划法。
第四条特征涉及到分治法的效率，如果各⼦问题是不独⽴的则分治法要做许多不必要的⼯作，重复地解公共的⼦问题，此时虽然可⽤分治法，但⼀般⽤动态规划法较好。
四、分治法的基本步骤分治法在每⼀层递归上都有三个步骤：step1 分解：将原问题分解为若⼲个规模较⼩，相互独⽴，与原问题形式相同的⼦问题；step2 解决：若⼦问题规模较⼩⽽容易被解决则直接解，否则递归地解各个⼦问题step3 合并：将各个⼦问题的解合并为原问题的解。
它的⼀般的算法设计模式如下：Divide-and-Conquer(P)1. if |P|≤n02. then return(ADHOC(P))3. 将P分解为较⼩的⼦问题 P1 ,P2 ,...,Pk4. for i←1 to k5. do yi ← Divide-and-Conquer(Pi) △递归解决Pi6. T ← MERGE(y1,y2,...,yk) △合并⼦问题7. return(T)其中|P|表⽰问题P的规模；n0为⼀阈值，表⽰当问题P的规模不超过n0时，问题已容易直接解出，不必再继续分解。
