《第二讲-分治专题讲座资料》由会员分享，可在线阅读，更多相关《第二讲-分治专题讲座资料（52页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析,第二讲 分 治,目的 分治法的思想 分治算法的设计方法 将递归算法改写成迭代算法的一般方法 重点 分治法的抽象控制策略 针对问题的抽象控制策略实现 难点 将递归算法改写成迭代算法的一般方法和实现,2.1 基本策略,一、求解大规模问题的复杂性,二、化整为零、分而治之,P n,p1 n1,p2 n2,pk nk,s0,s1,sk,S,分解,分治,合并,三、分治法的抽象控制策略,设： 原问题输入为an，简记为(1，n)； 子问题输入为apaq，1pqn，简记为(p，q)。,已知： SOLUTION; int divide (int, int); int small (int, int
2、); SOLUTION conquer (int, int); SOLUTION combine (SOLUTION, SOLUTION);,SOLUTION DandC(p,q) /* divide and conquer */ if(small(p,q) return conquer(p,q); else m=divide(p,q); return combine( DandC(p,m), DandC(m+1,q) ); ,分治法的抽象控制算法,已知n个按非降次序排列的元素an, 查找元素x是否在表中出现, 若找到, 返回其下标值, 否则, 返回一负数.,2.2 二分检索,一、问题,二、分
3、治的思路,原问题: (n, a0,an-1, x),数据分组: a0ak-2 ak-1 akan-1,三个子问题: (k-1, a0,ak-2, x) (1, ak-1, x) (n-k, ak,an-1, x),int BinSearch1(p, q, x) int k=(p+q)/2; if(qak) return BinSearch1(k+1, q, x); ,三、递归算法,四、计算复杂度,1. 二元比较树,以有序表的中间元素为根节点的二分树,左子树上所有元素不比父节点元素值大,右子树上所有元素不比父节点元素值小,圆形接点称为内节点,对应成功检索的数据元素,二分检索树的深度:,二元比较树
4、的深度:,方形接点称为外节点,对应不成功检索的数据子集,定理2.2 若n在区域2k-1, 2k)中, 则对于一次成功的检索, BinSearch1至多作k次比较; 而对于一次不成功的检索, 或者作k-1次比较或者作k次比较。,成功检索最好情况: 不成功检索最好情况: 成功检索最坏情况: 不成功检索最坏情况:,2. 时间复杂度,平均情况分析,内部路径长度之 和：I,5,2,7,1,3,6,8,4,9,外部路径长度之和：E, E=I+2n。,成功检索的平均比较次数： S(n)=(I/n)+1,不成功检索的平均比较次数: U(n)=E/(n+1),因为：U(n)=O(log n)，所以：S(n)=O
5、(log n),由此可得：S(n)=(1+1/n)U(n)-1,成功检索 不成功检索 最好 最坏 平均 最好 最坏 平均 O(1) O(log n) O(log n) O(log n) O(log n) O(log n),二分检索的时间复杂度结论,定理2.3 设an含有n(n1)个不同元素, 排序为a1an. 又设用以比较为基础去判断是否xan的任何算法在最坏情况下所需的最小比较次数为FIND(n), 那么, FIND(n) 。,说明：任何以比较为基础的检索算法, 最坏情况下的比较次数都不可能低于O(log n), 因此, 二分检索是最优的最坏情况算法。,3. 以比较为基础检索的时间下界,思考
6、题： 1. 请证明 E=I+2n 2. 请证明 S(n)=(I/n)+1,2.3 找最大和最小元素,在n个不同元素的集合an中同时找出它的最大和最小元素.,一、问题,比较次数：2(n-1),将语句1的体改写成 if(ai*max) *max=ai; else if(ai*min) *min=ai;,直接搜索的改进方法,三、实现分治的递归算法,集合只有一个元素时 *max=*min=ai；,集合只有两个元素时 if(aiaj) *max=aj; *min=ai; else *max=ai; *min=aj;,集合中有更多元素时 分治: 将原集合分解成两个子集, 分别求两个子集的最大和最小元素,
7、再合并结果。,递归算法,typedef struct ElemType max, min; SOLUTION;,SOLUTION MaxMin(i, j) SOLUTION s, s1, s2; if(i=j) s.max=s.min=ai; return s; if(i=j-1) if(ai=s2.max) ? (s.max=s1.max):( s.max=s2.max); (s1.min=s2.min) ? (s.min=s1.min):( s.min=s2.min); return s; ,时间复杂度,当n是2的幂时, 即对于某个正整数k, n=2k, 有,令t(n)表示MaxMin需要
8、的元素比较次数, 存在下列递推关系,t(n)=2t(n/2)+2 = 2(2t(n/4)+2)+2 = 4t(n/4)+4+2 =2k-1t(2)+ =2k-1+2k-2 =3n/2-2,当元素的比较开销与整数比较开销相当时, 将前两条if语句合并为： if(i=j-1) /* 对应一元素和两元素的情况 */ if(aiaj) s.max=aj; s.min=ai; else s.max=ai; s.min=aj; return s; ,MaxMin需要的比较次数, 存在下列递推关系：,思考题 请分析c(n)递推关系式中为什么是加3而不是加2 ?,给定一个含n个元素的集合an, 按一定次序(本
9、课程假定均为非降次序)将其分类(排序)。,2.4 分类,一、问题,二、插入分类,基本思想,InsertSort(int n) for(j=1; j=0) ,插入分类算法,三、归并分类,基本思想,归并分类递归算法,MergeSort (l, h) if (lh) m=(l+h)/2; MergeSort(l, m); MergeSort(m+1, h); Merge(l, m, h); ,已分类子集的归并过程,Merge (low, mid, high) ElemType bn; l=low; h=mid+1; k=l; while (lmid) while (h=high) bk+=ah+;
10、/* 转储剩余部分 */ else while(l=mid) bk+=al+; alow : high=blow : high; /* 将b数组转储到a */ ,已分类子集的归并算法,时间复杂度,缺点与改进,结合插入分类与归并分类各自的优点,四、快速分类,设计思路,实现部分分类的划分过程举例,实现部分分类的划分算法,Partition (p, q) r=ap; j=p+1; k=q; while(1) while (j=r) k-; if (jk) t=aj; aj=ak; ak=t; j+; k-; else break; ap=ak; ak=r; return k; ,快速分类算法,Qui
11、ckSort (p, q) if(pq) j=Partition (p, q); QuickSort(p,j-1); QuickSort(j+1,q); ,时间复杂度,最坏情况 ： CW(n)=n+n-1+3+2=O(n2).,假设n个元素各不相同，划分元素随机选取，取第k (1kn)个元素是等概率的，计算时间C(n)取决于Partition的元素比较次数.,平均情况：,经推导可得: CA(n)2(n+1)loge(n+1)= O(nlogn),结论： 快速分类算法的最坏情况时间为O(n2), 平均情况为O(nlogn).,五、几种分类算法的时间复杂度比较,结论：以比较为基础的分类算法在最坏情
12、况下的时间下界为O(nlogn), 是最坏情况下的最优算法。,一、问题,2.5 选择,给定一个含n个元素的集合an, 找出其中第k小的元素，并将其转储到ak。,三、基于分治思想的选择算法,基本思路,用partition算法实现分治,selection (p, q, k) int j; j=partition (p, q); if (k=j) return; if (kj) selection (p, j-1, k); else selection (j+1, q, k); ,分治算法,思考题： 1. 过程MergeSort的时间复杂度是以什么计算操作频数度量的, 最好情况、最坏情况、平均时间复
13、杂度是多少? 2. 用C语言实现merge过程时，数组b定义为局部变量时，最小存储量需求为多少？可否定义为外部数组，最小存储量需求为多少？,一、递归算法的特点,2.6 消除递归,符合人的递推求解问题的自然思维习惯 算法的结构简单，代码精炼，可读性好 效率低,递归的基本思路分治,输出s=”abc”的递归过程,void reverse (char * s) extern ElemType stack2*n+1, top=0; L1: if( *s!=0 ) stack+top=s; stack+top=L2; s=s+1; goto L1; L2: putchar(*s); / 接下来处理返回语句
14、 if(top=0 ) return; / 栈为空 else addr=stacktop-; / 恢复地址 s=stacktop-; / 恢复参数 if(addr = L2) goto L2; ,改写的迭代算法,void reverse(char * s) int top=0; while(*s!=0) top+; s+; while (top!=0) putchar(*s); s-; top-; ,优化后的迭代算法,例2：写一个求数组an中的最大元素的递归算法并将其改写成迭代算法。,分治的思路:,思考题： 为什么k不作为局部变量在L1之后入栈，可否象i, j一样处理？,int max (in
15、t i) int j, k=n-1; for (j=n-2; j=i; j-) if (ajak) k=j; return k; ,优化后的迭代算法,例3：将分治算法的抽象递归过程改写为迭代过程。,SOLUTION DandC (p, q) /* divide and conquer */ int m; SOLUTION s1, s2, s; if( small (p, q) ) s=conquer (p, q); else m=divide (p, q); s1=DandC (p, m); s2=DandC (m+1, q); s=combine (s1, s2); return s; ,抽象控制递归算法,SO
