-分治收集讲座.ppt
算法设计与分析,第二讲 分 治,目的 分治法的思想 分治算法的设计方法 将递归算法改写成迭代算法的一般方法 重点 分治法的抽象控制策略 针对问题的抽象控制策略实现 难点 将递归算法改写成迭代算法的一般方法和实现,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); 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 二分检索,一、问题,二、分治的思路,原问题: (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. 二元比较树,以有序表的中间元素为根节点的二分树,左子树上所有元素不比父节点元素值大,右子树上所有元素不比父节点元素值小,圆形接点称为内节点,对应成功检索的数据元素,二分检索树的深度:,二元比较树的深度:,方形接点称为外节点,对应不成功检索的数据子集,定理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(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)个不同元素, 排序为a1<<an. 又设用以比较为基础去判断是否xan的任何算法在最坏情况下所需的最小比较次数为FIND(n), 那么, FIND(n) 。,说明：任何以比较为基础的检索算法, 最坏情况下的比较次数都不可能低于O(log n), 因此, 二分检索是最优的最坏情况算法。,3. 以比较为基础检索的时间下界,思考题： 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(ai<aj) *max=aj; *min=ai; else *max=ai; *min=aj;,集合中有更多元素时 分治: 将原集合分解成两个子集, 分别求两个子集的最大和最小元素, 再合并结果。,递归算法,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需要的元素比较次数, 存在下列递推关系,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(ai<aj) s.max=aj; s.min=ai; else s.max=ai; s.min=aj; return s; ,MaxMin需要的比较次数, 存在下列递推关系：,思考题 请分析c(n)递推关系式中为什么是加3而不是加2 ?,给定一个含n个元素的集合an, 按一定次序(本课程假定均为非降次序)将其分类(排序)。,2.4 分类,一、问题,二、插入分类,基本思想,InsertSort(int n) for(j=1; j=0) ,插入分类算法,三、归并分类,基本思想,归并分类递归算法,MergeSort (l, h) if (l<h) 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+; /* 转储剩余部分 */ 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 (j<k) t=aj; aj=ak; ak=t; j+; k-; else break; ap=ak; ak=r; return k; ,快速分类算法,QuickSort (p, q) if(p<q) 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).,五、几种分类算法的时间复杂度比较,结论：以比较为基础的分类算法在最坏情况下的时间下界为O(nlogn), 是最坏情况下的最优算法。,一、问题,2.5 选择,给定一个含n个元素的集合an, 找出其中第k小的元素，并将其转储到ak。,三、基于分治思想的选择算法,基本思路,用partition算法实现分治,selection (p, q, k) int j; j=partition (p, q); if (k=j) return; if (k<j) selection (p, j-1, k); else selection (j+1, q, k); ,分治算法,思考题： 1. 过程MergeSort的时间复杂度是以什么计算操作频数度量的, 最好情况、最坏情况、平均时间复杂度是多少? 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); / 接下来处理返回语句 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 (int 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; ,抽象控制递归算法,SOLUTION DandC (p, q) extern ElemType stack5*n+1, top=0; int m; SOLUTION s1, s2; L1: if(small(p,q) s=conquer(p,q); else m=divide(p,q); stack+top=p; stack+top=q; stack+top=m; stack+top=L2; p=p; q=m; goto L1; L2: s1= stacktop-; stack+top=p; stack+top=q; stack+top=m; stack+top=L3; p=m+1; q=q; goto L1; L3: s2=stacktop-; s=combine(s1,s2); ,if(top=0) return s； else addr=stacktop-; m=stacktop-; q=stacktop-; p=stacktop-; stack+top=s; if(addr=L2) goto L2; else goto L3; ,抽象控制迭代算法,作业 设计、实现归并分类和快速分类算法，设计测试数据集，比较二种分类算法的实际运行效率差异。 参考实验报告格式文件，提交设计报告的A4打印稿, 由班干部收集后统一提交，不单独受理。,
