《分治专题讲座》PPT课件.ppt

《《分治专题讲座》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《分治专题讲座》PPT课件.ppt（52页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、算法设计与分析算法设计与分析第二讲第二讲 分分 治治l 目的目的 分治法的思想分治法的思想分治算法的设计方法分治算法的设计方法将递归算法改写成迭代算法的一般方法将递归算法改写成迭代算法的一般方法l 重点重点 分治法的抽象控制策略分治法的抽象控制策略针对问题的抽象控制策略实现针对问题的抽象控制策略实现l 难点难点将递归算法改写成迭代算法的一般方法和实现将递归算法改写成迭代算法的一般方法和实现2.1 基本策略基本策略 一、求解大规模问题的复杂性一、求解大规模问题的复杂性二、化整为零、分而治之二、化整为零、分而治之 Pnp1n1p2n2pknks0s1skS 分解分解分治分治合并合并三、分治法的抽象

2、控制策略三、分治法的抽象控制策略设：设：原问题输入为原问题输入为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 c

3、ombine(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)i

4、nt 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圆形接点称为内节点圆形接点称为内节点,对应成功检索的数据元素对应成功检索的数据元素二分检索树的深度二分检索树的深度:二元比较

5、树的深度二元比较树的深度:9方形接点称为外节点方形接点称为外节点,对应不成功检索的数据子集对应不成功检索的数据子集n n定理定理定理定理2.22.2 n n 若若若若 n n在在在在 区区区区 域域域域 22k-1k-1,2 2k k)中中中中,则则则则 对对对对 于于于于 一一一一 次次次次 成成成成 功功功功 的的的的 检检检检 索索索索,BinSearch1BinSearch1至至至至多多多多作作作作k k次次次次比比比比较较较较;而而而而对对对对于于于于一一一一次次次次不不不不成成成成功功功功的的的的检检检检索索索索,或或或或者者者者作作作作k-1k-1次比较或者作次比较或者作次比较或

6、者作次比较或者作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

7、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.又设用又设用又设用又设用以比较为基础去判断是否以比较为基础去判断是否以比

8、较为基础去判断是否以比较为基础去判断是否x xanan的任何算法在最坏情况下所的任何算法在最坏情况下所的任何算法在最坏情况下所的任何算法在最坏情况下所需的最小比较次数为需的最小比较次数为需的最小比较次数为需的最小比较次数为FIND(n),FIND(n),那么那么那么那么,FIND(n),FIND(n)。说明：说明：任何以比较为基础的检索算法任何以比较为基础的检索算法,最坏情况下的比较次数都最坏情况下的比较次数都不可能低于不可能低于O(log n),因此因此,二分检索是最优的最坏情况算法。二分检索是最优的最坏情况算法。3.以比较为基础检索的时间下界以比较为基础检索的时间下界n n思考题：思考题：

9、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;最好情况：最好情况：最坏情况：最坏情况：平均情

10、况：平均情况：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 集合中有更多元素时集合中有更多元素时 分治分治:将原集合分解成两个子集将原集合分解成两个子集,分别求两个子集的最大分别求两个子集的最大和最小元素和最小元素,再合并结果。再合并结果。递归算法递归

11、算法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需要的比较次数需要的比较次数,存在下列递推关系：存在下列递推关系：思考题思考题 请分析请

12、分析c(n)递推关系式中为什么是加递推关系式中为什么是加3而不是加而不是加2?l l 给定一个含给定一个含给定一个含给定一个含n n个元素的集合个元素的集合个元素的集合个元素的集合an,an,按一定次序按一定次序按一定次序按一定次序(本课程假定本课程假定本课程假定本课程假定均为非降次序均为非降次序均为非降次序均为非降次序)将其分类将其分类将其分类将其分类(排序排序排序排序)。2.4 分类分类一、问题一、问题l二、插入分二、插入分类类 基本思想基本思想已分已分类类的部分的部分未分未分类类的部分的部分a1aj-1ajaj+1anInsertSort(int n)for(j=1;j=0)&(unso

13、rted 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);已分类子集的归并过程已分

14、类子集的归并过程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+;/

15、*转储剩余部分*/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

16、=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)

17、=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

18、)最坏最坏O(n2)O(nlogn)O(n2)平均平均O(nlogn)O(nlogn)结论：结论：以比较为基础的分类算法在最坏情况下的时间下界为以比较为基础的分类算法在最坏情况下的时间下界为O(nlogn),是最坏情况下的最优算法是最坏情况下的最优算法。l一、问题一、问题2.5 选择选择 给定一个含给定一个含n个元素的集合个元素的集合an,找出其中第找出其中第k小的元素，并将其小的元素，并将其转储到转储到ak。二、最直观的求解算法二、最直观的求解算法按非降次序分类按非降次序分类ak即为第即为第k小的元素小的元素完全分类做了不必要的运算，效率低完全分类做了不必要的运算，效率低l三、基于分治思想的

19、选择算三、基于分治思想的选择算法法原始原始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(

20、j+1,q,k);else selection(j+1,q,k);n n 分治算法分治算法四、时间复杂度四、时间复杂度最坏情况：最坏情况：O(n2)最好，平均情况：最好，平均情况：O(n)思考题：思考题：1.过程过程MergeSort的时间复杂度是以什么计算操作频数度量的的时间复杂度是以什么计算操作频数度量的,最好情况、最坏情况、平均时间复杂度是多少最好情况、最坏情况、平均时间复杂度是多少?2.用用C语言实现语言实现merge过程时，数组过程时，数组b定义为局部变量时，最小存定义为局部变量时，最小存储量需求为多少？可否定义为外部数组，最小存储量需求为多储量需求为多少？可否定义为外部数组，最小存

21、储量需求为多少？少？l一、递归算法的特一、递归算法的特点点2.6 消除递归消除递归l 符合人的递推求解问题的自然思维习惯符合人的递推求解问题的自然思维习惯l 算法的结构简单，代码精炼，可读性好算法的结构简单，代码精炼，可读性好l 效率低效率低二、消除递归的一般步骤二、消除递归的一般步骤例例1：写一个递归函数写一个递归函数 reverse(char*s)，按逆序输出一个字，按逆序输出一个字符串，并将此递归算法改写成相应的迭代算法。符串，并将此递归算法改写成相应的迭代算法。递归的基本思路递归的基本思路递归的基本思路递归的基本思路分治分治分治分治S为空字符串吗？为空字符串吗？按逆序输出除按逆序输出除

22、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)sta

23、ck4=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

24、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)got

25、o 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：写一个求数组：写一个求数组：写一个

26、求数组：写一个求数组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)定定义义和初始化堆和初始化堆栈栈(存存储储参数、局部参数、局部变变量、返回量、返回

27、值值和返址和返址).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)如果是如果是带带返回返回值值的的调调用，从用，从栈顶栈顶取回返取回返回回值值并代替并代替调调用，其余代

28、用，其余代码码按原方式按原方式处处理，理，并将并将(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 优化后的迭代算法优化

29、后的迭代算法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

30、,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打印稿打印稿,由班干部由班干部收集后统一提交，不单独受理。收集后统一提交，不单独受理。