二分治专题座PPT课件.ppt

算法设计与分析第二讲 分 治l 目的 分治法的思想分治算法的设计方法将递归算法改写成迭代算法的一般方法l 重点 分治法的抽象控制策略针对问题的抽象控制策略实现l 难点将递归算法改写成迭代算法的一般方法和实现2.1 基本策略 一、求解大规模问题的复杂性二、化整为零、分而治之 Pnp1n1p2n2pknks0s1skS 分解分治合并三、分治法的抽象控制策略设：原问题输入为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 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(qp)return 1;/*参数错误*/if(x=ak)return k;if(xak)return BinSearch1(k+1,q,x);三、递归算法l四、计算复杂度1.二元比较树l 以有序表的中间元素为根节点的二分树l 左子树上所有元素不比父节点元素值大l 右子树上所有元素不比父节点元素值小527136849圆形接点称为内节点,对应成功检索的数据元素二分检索树的深度:二元比较树的深度:9方形接点称为外节点,对应不成功检索的数据子集n n定理定理2.22.2 n n 若若n n在在区区域域22k-1k-1,2 2k k)中中,则则对对于于一一次次成成功功的的检检索索,BinSearch1BinSearch1至至多多作作k k次次比比较较;而而对对于于一一次次不不成成功功的的检检索索,或或者者作作k-1k-1次次比比较较或者作或者作k k次比较。次比较。成功检索最好情况:不成功检索最好情况:成功检索最坏情况:不成功检索最坏情况:2.时间复杂度平均情况分平均情况分析析内部路径长度之和：I527136849外部路径长度之和：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)二分检索的时间复杂度结二分检索的时间复杂度结论论n n定理定理2.32.3 n n 设设anan含有含有n(n1)n(n1)个不同元素个不同元素,排序为排序为a1an.a1an.又设用又设用以比较为基础去判断是否以比较为基础去判断是否x xanan的任何算法在最坏情况下所的任何算法在最坏情况下所需的最小比较次数为需的最小比较次数为FIND(n),FIND(n),那么那么,FIND(n),FIND(n)。说明：任何以比较为基础的检索算法,最坏情况下的比较次数都不可能低于O(log n),因此,二分检索是最优的最坏情况算法。3.以比较为基础检索的时间下界n n思考题：n n n n 1.1.请证明请证明 E=I+2n E=I+2nn n 2.2.请证明请证明 S(n)=(I/n)+1 S(n)=(I/n)+1n2.3 找最大和最小元素在n个不同元素的集合an中同时找出它的最大和最小元素.一、问题二、直接搜索 StraitSearch(n,&max,&min)*max=*min=a0;for(i=1;i*max)*max=ai;if(ai*max)*max=ai;else if(ai*min)*min=ai;最好情况：最坏情况：平均情况：n-12(n-1)3/2(n-1)由此可见,直接搜索的时间复杂度为:O(n)直接搜索的改进方法l三、实现分治的递归算法 l 集合只有一个元素时 *max=*min=ai；l 集合只有两个元素时 if(aiaj)*max=aj;*min=ai;else *max=ai;*min=aj;l 集合中有更多元素时 分治:将原集合分解成两个子集,分别求两个子集的最大和最小元素,再合并结果。递归算法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=j-1)/*对应一元素和两元素的情况*/if(aiaj)s.max=aj;s.min=ai;else s.max=ai;s.min=aj;return s;MaxMin需要的比较次数,存在下列递推关系：思考题 请分析c(n)递推关系式中为什么是加3而不是加2?l l 给定一个含给定一个含n n个元素的集合个元素的集合an,an,按一定次序按一定次序(本课程假定本课程假定均为非降次序均为非降次序)将其分类将其分类(排序排序)。2.4 分类一、问题l二、插入分类 基本思想已分类的部分未分类的部分a1aj-1ajaj+1anInsertSort(int n)for(j=1;j=0)&(unsorted ak);k-)ak+1=ak;ak+1=unsorted;插入分类算法考虑内层for循环中元素比较的次数T(n)最好情况：最坏情况：T(n)=O(n)T(n)=1+2+n-1=O(n2)时间复杂度l三、归并分类 基本思想a l a a a h 归并分类归并分类按非降次序合并两个已分类的子集 归并分类递归算法 MergeSort(l,h)if(lh)m=(l+h)/2;MergeSort(l,m);MergeSort(m+1,h);Merge(l,m,h);已分类子集的归并过程A1345691027811121314指针l=1,h=8,k=1B1指针l=2,h=8,k=2B12指针l=2,h=9,k=3B123456指针l=5,h=9,k=7B12345678指针l=5,h=11,k=9B12345678910指针l=8,h=11,k=11B1234567891011121314指针l=8,h=15,k=15Merge(low,mid,high)ElemType bn;l=low;h=mid+1;k=l;while(l=mid)&(h=high)/*部分合并*/if(almid)while(h=high)bk+=ah+;/*转储剩余部分*/else while(l=mid)bk+=al+;alow:high=blow:high;/*将b数组转储到a*/已分类子集的归并算法 时间复杂度 缺点与改进结合插入分类与归并分类各自的优点l四、快速分类 设计思路a1aj-1ajaj+1an使a1:j-1ajaj使aj+1:naj对a1:j-1快速分类aj对aj+1:n 快速分类已分类的集合 实现部分分类的划分过程举例原始41362578指针r=4jk一次循 环r=4jkr=41326578二 次循 环kj交换位 置213r=46578返回交换位置 k 实现部分分类的划分算法 Partition(p,q)r=ap;j=p+1;k=q;while(1)while(j=k)&(aj=r)j+;while(j=r)k-;if(jk)t=aj;aj=ak;ak=t;j+;k-;else break;ap=ak;ak=r;return k;快速分类算法QuickSort(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).l五、几种分类算法的时间复杂度比较 插入分类归并分类快速分类最好O(n)最坏O(n2)O(nlogn)O(n2)平均O(nlogn)O(nlogn)结论：以比较为基础的分类算法在最坏情况下的时间下界为O(nlogn),是最坏情况下的最优算法。l一、问题2.5 选择 给定一个含n个元素的集合an,找出其中第k小的元素，并将其转储到ak。二、最直观的求解算法按非降次序分类ak即为第k小的元素完全分类做了不必要的运算，效率低l三、基于分治思想的选择算法原始a1aj-1ajaj+1anpartition使a1:j-1aj分治kj,在aj+1:n中选择基本思路用partition算法实现分治n nselection(p,q,k)selection(p,q,k)n n int j;int j;n n j=partition(p,q);j=partition(p,q);n n if(k=j)return;if(k=j)return;n n if(kj)selection(p,j-1,k);if(kj)selection(p,j-1,k);n n else selection(j+1,q,k);else selection(j+1,q,k);n n 分治算法四、时间复杂度最坏情况：O(n2)最好，平均情况：O(n)思考题：1.过程MergeSort的时间复杂度是以什么计算操作频数度量的,最好情况、最坏情况、平均时间复杂度是多少?2.用C语言实现merge过程时，数组b定义为局部变量时，最小存储量需求为多少？可否定义为外部数组，最小存储量需求为多少？l一、递归算法的特点2.6 消除递归l 符合人的递推求解问题的自然思维习惯l 算法的结构简单，代码精炼，可读性好l 效率低二、消除递归的一般步骤例1：写一个递归函数 reverse(char*s)，按逆序输出一个字符串，并将此递归算法改写成相应的迭代算法。递归的基本思路递归的基本思路分治分治S为空字符串吗？按逆序输出除S0外的子字符串输出S0返回YESNO递归算法void reverse(char*s)if(*s!=0)reverse(s+1);putchar(*s);return;输出输出s=”abc”s=”abc”的递归过的递归过程程进入递归调用,top=0递归调用返回,top=6顺序条件栈中元素top=,s=顺序条件addr,s 1*s=astack1=s,(a)stack2=L2,(putchar)2,s+11top=6addr=stack6s=stack52*s=bstack3=s,(b)stack4=L2,(putchar)4,s+22top=4addr=stack4s=stack33*s=cstack5=s,(c)stack6=L2,(putchar)6,s+33top=2addr=stack2s=stack14*s=0调用结束，转返回处理4top=0完全返回n nvoid reverse(char*s)void reverse(char*s)n n extern ElemType stack2*n+1,top=0;extern ElemType stack2*n+1,top=0;n n L1:L1:n n if(*s!=0)if(*s!=0)n n stack+top=s;stack+top=L2;s=s+1;stack+top=s;stack+top=L2;s=s+1;n n goto L1;goto L1;n n L2:L2:n n putchar(*s);putchar(*s);n n /接下来处理返回语接下来处理返回语句句n n if(top=0)return;/if(top=0)return;/栈为空栈为空n n else elsen n addr=stacktop-;/addr=stacktop-;/恢复地址恢复地址n n s=stacktop-;/s=stacktop-;/恢复参数恢复参数n n if(addr=L2)goto L2;if(addr=L2)goto L2;n n n n 改写的迭代算法n nvoid reverse(char*s)void reverse(char*s)n n int top=0;int top=0;n n while(*s!=0)while(*s!=0)n n top+;top+;n n s+;s+;n n n n while(top!=0)while(top!=0)n n putchar(*s);putchar(*s);n n s-;top-;s-;top-;n n n n 优化后的迭代算法n n 例例2 2：写一个求数组：写一个求数组anan中的最大元素的递归算法并将其改写中的最大元素的递归算法并将其改写成迭代算法。成迭代算法。ai ai+1 an-1 分治的思路:int max(int i)int j=i,k;if(iaj)k=i;else k=j;else k=n-1;return k;递归算法:(0)开始，照搬（所有不涉及递归调用和返回语句的代码都照搬）(1)定义和初始化堆栈(存储参数、局部变量、返回值和返址).int max(int i)extern stack4*n+1,top=0;int j=i,k;(2)对第一条可执行语句定义标号L1,每次递归调用执行步骤(3).(3)将所有参数和局部变量进栈.(4)建立第i个返回地址的标号Li，进栈.(5)计算本次递归调用实参的值，并赋给形参变量.(6)无条件转移到L1进入递归.(7)如果是带返回值的调用，从栈顶取回返回值并代替调用，其余代码按原方式处理，并将(4)建立的标号附于该语句；如果是不带返回值的调用，则将(4)建立的标号直接附于(6)对应的语句之后的那条语句.L1:if(in-1)stack+top=i;stack+top=j;stack+top=L2;i=i+1;goto L1；L2:j=stacktop-;if(ai=i;j-)for(j=n-2;j=i;j-)n n if(ajak)if(ajak)n n k=j;k=j;n n return k;return k;n n 优化后的迭代算法n n 例例3 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打印稿,由班干部收集后统一提交，不单独受理。