分治专题讲座PPT学习教案

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

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);第3页/共52页 SOLUTION DandC(p,q) /* divide and conquer */ if(small(p,q) return conqu

3、er(p,q); else m=divide(p,q); return combine( DandC(p,m), DandC(m+1,q) ); 分治法的抽象控制算法分治法的抽象控制算法第4页/共52页 已知已知n个按非降次序排列的元素个按非降次序排列的元素an, 查找元素查找元素x是否在表是否在表中出现中出现, 若找到若找到, 返回其下标值返回其下标值, 否则否则, 返回一负数返回一负数. 2.2 2.2 二分检索二分检索一、问一、问题题第5页/共52页二、分治的思路二、分治的思路原问题原问题: (n, a0,an-1, x)数据分组数据分组: a0ak-2 ak-1 akan-1三个子问题

4、三个子问题: (k-1, a0,ak-2, x) (1, ak-1, x) (n-k, ak,an-1, x)第6页/共52页 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); 三、递归算法三、递归算法第7页/共52页四、计算复杂四、计算复杂度度1. 二元比较树l 以有序表的中间元素为根节点的二分树以有序表的中间元素为根节点的二分树l 左子树上所有元素不比父节点元素值大左子树上所有元素不比父节点元素

5、值大l 右子树上所有元素不比父节点元素值小右子树上所有元素不比父节点元素值小第8页/共52页527136849圆形接点称为内节点圆形接点称为内节点, ,对应成功检索的数据元素对应成功检索的数据元素二分检索树的深度二分检索树的深度:1n log二元比较树的深度二元比较树的深度: 2n log9方形接点称为外节点方形接点称为外节点, ,对应不成功检索的数据子集对应不成功检索的数据子集第9页/共52页定理定理2.2 若若n在区域在区域2k-1, 2k)中中, 则对于一次成功的检索则对于一次成功的检索, BinSearch1至至多作多作k次比较次比较; 而对于一次不成功的检索而对于一次不成功的检索,

6、或者作或者作k-1次比较或者次比较或者作作k次比较。次比较。(1)( log )(log )O kOnOn( )( log n1)(log )O kOOn( )( log n1)(log )O kOOn成功检索最好情况成功检索最好情况:不成功检索最好情况不成功检索最好情况: 成功检索最坏情况成功检索最坏情况: 不成功检索最坏情况不成功检索最坏情况: ) 1 (O2. 时间复杂时间复杂度度第10页/共52页平均情况分析平均情况分析内部路径长度之内部路径长度之和：和：I527136849外部路径长度之外部路径长度之和：和：E, E=I+2n。成功检索的平成功检索的平均比较次数：均比较次数：S(n)

7、=(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第11页/共52页 成功检索成功检索 不成功检索不成功检索 最好最好 最坏最坏 平均平均 最好最好 最坏最坏 平均平均 O(1) O(log n) O(log n) O(log n) O(log n) O(log n)二分检索的时间复杂度结论二分检索的时间复杂度结论第12页/共52页定理定理2.3 设设an含有含有n(n1)个不同元素个不同元素, 排序为排序为a1an.

8、又设用以又设用以比较为基础去判断是否比较为基础去判断是否xan的任何算法在最坏情况下所需的的任何算法在最坏情况下所需的最小比较次数为最小比较次数为FIND(n), 那么那么, FIND(n) 。) 1log( n说明：说明：任何以比较为基础的检索算法任何以比较为基础的检索算法, 最坏情况下的比较次数最坏情况下的比较次数都不可能低于都不可能低于O(log n), 因此因此, 二分检索是最优的最坏情况算法二分检索是最优的最坏情况算法。3. 以比较为基础检索的时间下界以比较为基础检索的时间下界第13页/共52页思考题：思考题： 1. 请证明请证明 E=I+2n 2. 请证明请证明 S(n)=(I/n

9、)+1第14页/共52页2.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)直

10、接搜索的改进方直接搜索的改进方法法第16页/共52页三、实现分治的递三、实现分治的递归算法归算法 l 集合只有一个元素时集合只有一个元素时 *max=*min=ai；l 集合只有两个元素时集合只有两个元素时 if(aiaj) *max=aj; *min=ai; else *max=ai; *min=aj;l 集合中有更多元素时集合中有更多元素时 分治分治: 将原集合分解成两个子集将原集合分解成两个子集, 分别求两个子集的最大分别求两个子集的最大和最小元素和最小元素, 再合并结果。再合并结果。第17页/共52页 递归算法递归算法typedef struct ElemType max, min;

11、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; 22( ) 5 /232 ( /2)32nc nnc nn MaxMin需要的比较次数需要的比较次数, 存在下列递推关系

12、：存在下列递推关系：第20页/共52页思考题思考题 请分析请分析c(n)递推关系式中为什么是加递推关系式中为什么是加3而不是加而不是加2 ? 第21页/共52页 给定一个含给定一个含n个元素的集合个元素的集合an, 按一定次序按一定次序(本课程假定均本课程假定均为非降次序为非降次序)将其分类将其分类(排序排序)。2.4 分类分类一、问题一、问题第22页/共52页二、插入二、插入分类分类 基本思想基本思想已分类的部分已分类的部分未分类的部分未分类的部分a1aj-1ajaj+1an第23页/共52页InsertSort(int n) for(j=1; j=0)&(unsorted ak); k-

13、) ak+1=ak; ak+1= unsorted; 插入分类算法插入分类算法考虑内层考虑内层for循环中元素比较的次数循环中元素比较的次数T(n)最好情况最好情况：最坏情况：最坏情况：T(n)=O(n)T(n)=1+2+n-1=O(n2) 时间复杂度时间复杂度第24页/共52页三、归并分三、归并分类类 基本思想基本思想a l a a a h 归并分类归并分类按非降次序合并两个已分类的子集2lh2lh第25页/共52页 归并分类递归算法归并分类递归算法 MergeSort (l, h) if (lh) m=(l+h)/2; MergeSort(l, m); MergeSort(m+1, h);

14、 Merge(l, m, h); 第26页/共52页 已分类子集的归并过程已分类子集的归并过程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=15第27页/共52页Merge (low, mid, high) ElemType bn; l=low; h=mi

15、d+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 */ 已分类子集的归并算法已分类子集的归并算法第28页/共52页 时间复杂度时间复杂度kn 21,( )2 ( /2)1, ( log )anaT nT ncnncO nn为常数是常数 缺点与改进缺点与改进结合插入分类与归并分类各自的优点结合插入分类与归并分类各自的优点第29页/共5

16、2页四、快速分四、快速分类类 设计思路设计思路a1aj-1ajaj+1an使使a1:j-1ajaj使使aj+1:naj对对a1:j-1快速分类快速分类aj对对aj+1:n 快速分类快速分类已分类的集合已分类的集合第30页/共52页 实现部分分类的划分过程举例实现部分分类的划分过程举例原始41362578指针r=4jk一次循 环r=4jkr=41326578二 次循 环kj交换位 置213r=46578返回交换位置 k第31页/共52页 实现部分分类的划分算法实现部分分类的划分算法 Partition (p, q) r=ap; j=p+1; k=q; while(1) while (j=k) &

17、 (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;第32页/共52页 快速分类算法快速分类算法QuickSort (p, q) if(pq) j=Partition (p, q); QuickSort(p,j-1); QuickSort(j+1,q); 第33页/共52页 时间复杂度时间复杂度最坏情况最坏情况 ： CW(n)=n+n-1+3+2=O(n2). 假设假设n个元素各不相同，划分元素随机选取，取第个元素各不相同，划分元素随机选取，取第k (1

18、kn)个元个元素是等概率的，计算时间素是等概率的，计算时间C(n)取决于取决于Partition的元素比较次数的元素比较次数.平均情况：平均情况： )() 1(11)(1knCkCnnnCAnkAA经推导可得经推导可得: CA(n)2(n+1)loge(n+1)= O(nlogn) 结论：结论： 快速分类算法的最坏情况时间为快速分类算法的最坏情况时间为O(n2), 平均情况为平均情况为O(nlogn).第34页/共52页五、几种分类算法的时间复五、几种分类算法的时间复杂度比较杂度比较 插入分类插入分类归并分类归并分类快速分类快速分类最好最好O(n)最坏最坏O(n2)O(nlogn)O(n2)平

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

20、治思想的选择算法选择算法原始原始a1aj-1ajaj+1anpartition使使a1:j-1aj分治分治kj,在在aj+1:n中选择中选择基本思路基本思路用用partition算法实现分治算法实现分治第37页/共52页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); 分治算法分治算法四、时间复杂度四、时间复杂度最坏情况：最坏情况：O(n2)最好，平均情况：最好，平均情况：O(n)第38页/共52页思

21、考题：思考题： 1. 过程过程MergeSort的时间复杂度是以什么计算操作频数度量的的时间复杂度是以什么计算操作频数度量的, 最最好情况、最坏情况、平均时间复杂度是多少好情况、最坏情况、平均时间复杂度是多少? 2. 用用C语言实现语言实现merge过程时，数组过程时，数组b定义为局部变量时，最小定义为局部变量时，最小存储量需求为多少？可否定义为外部数组，最小存储量需求存储量需求为多少？可否定义为外部数组，最小存储量需求为多少？为多少？第39页/共52页一、递归算法一、递归算法的特点的特点2.6 消除递消除递归归l 符合人的递推求解问题的自然思维习惯符合人的递推求解问题的自然思维习惯l 算法的

22、结构简单，代码精炼，可读性好算法的结构简单，代码精炼，可读性好l 效率低效率低二、消除递归的一般步骤二、消除递归的一般步骤例例1：写一个递归函数写一个递归函数 reverse (char * s)，按逆序输出一个字，按逆序输出一个字符串，并将此递归算法改写成相应的迭代算法。符串，并将此递归算法改写成相应的迭代算法。第40页/共52页递归的基本思路递归的基本思路分治分治S为空字符串吗？为空字符串吗？按逆序输出除按逆序输出除S0外的子字符外的子字符串串输出输出S0返回返回YESNO递归算法递归算法void reverse (char * s) if( *s!=0 ) reverse(s+1); p

23、utchar (*s); return;第41页/共52页输出输出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 , (p

24、utchar)6, s+33top=2addr=stack2s=stack14*s=0调用结束，转返回处理调用结束，转返回处理4top=0完全返回完全返回第42页/共52页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-; /

25、 恢复参数 if(addr = L2) goto L2; 改写的迭代算法改写的迭代算法第43页/共52页void reverse(char * s) int top=0; while(*s!=0) top+; s+; while (top!=0) putchar(*s); s-; top-; 优化后的迭代算法优化后的迭代算法第44页/共52页 例例2：写一个求数组：写一个求数组an中的最大元素的递归算法并将其改写中的最大元素的递归算法并将其改写成迭代算法。成迭代算法。ai ai+1 an-1 分治的思路分治的思路:int max (int i) int j=i, k; if(iaj) k=i;

26、 else k=j; else k=n-1; return k; 递归算法递归算法:第45页/共52页(0) 开始，照搬（所有不涉及递归调用和返开始，照搬（所有不涉及递归调用和返回语句的代码都照搬）回语句的代码都照搬）(1) 定义和初始化堆栈定义和初始化堆栈(存储参数、局部变存储参数、局部变量、返回值和返址量、返回值和返址).int max(int i) extern stack4*n+1, top=0; int j=i, k;(2) 对第一条可执行语句定义标号对第一条可执行语句定义标号L1,每次每次递归调用执行步骤递归调用执行步骤 (3). (3) 将所有参数和局部变量进栈将所有参数和局部变

27、量进栈. (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-) if (ajak) k=j; return k; 优化后的迭代算法优化后的迭代算法第48页/共52页 例例3：将分治算法的抽象递归过程改写为迭代过程