第二讲分治专题讲座课件.ppt

算法设计与分析算法设计与分析第二讲第二讲 分分 治治l 目的目的 分治法的思想分治法的思想分治算法的设计方法分治算法的设计方法将递归算法改写成迭代算法的一般方法将递归算法改写成迭代算法的一般方法l 重点重点 分治法的抽象控制策略分治法的抽象控制策略针对问题的抽象控制策略实现针对问题的抽象控制策略实现l 难点难点将递归算法改写成迭代算法的一般方法和实现将递归算法改写成迭代算法的一般方法和实现2.1 基本策略基本策略 一、求解大规模问题的复杂性一、求解大规模问题的复杂性二、化整为零、分而治之二、化整为零、分而治之 Pnp1n1p2n2pknks0s1skS 分解分解分治分治合并合并三、分治法的抽象控制策略三、分治法的抽象控制策略设：设： 原问题输入为原问题输入为a[n]，简记为，简记为(1，，n)；； 子问题输入为子问题输入为a[p]~a[q]，，1≤p≤q≤n，简记为，简记为(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个按非降次序排列的元素个按非降次序排列的元素a[n], 查找元素查找元素x是否在表中是否在表中出现出现, 若找到若找到, 返回其下标值返回其下标值, 否则否则, 返回一负数返回一负数. 2.2 2.2 二分检索二分检索一、问题一、问题二、分治的思路二、分治的思路原问题原问题: (n, a[0],…,a[n-1], x)数据分组数据分组: a[0]~a[k-2] a[k-1] a[k]~a[n-1]三个子问题三个子问题: (k-1, a[0],…,a[k-2], x) (1, a[k-1], x) (n-k, a[k],…,a[n-1], x) int BinSearch1(p, q, x){ int k=(p+q)/2; if(qa[k]) return BinSearch1(k+1, q, x);} 三、递归算法三、递归算法l四、计算复杂度四、计算复杂度1. 二元比较树l 以有序表的中间元素为根节点的二分树以有序表的中间元素为根节点的二分树l 左子树上所有元素不比父节点元素值大左子树上所有元素不比父节点元素值大l 右子树上所有元素不比父节点元素值小右子树上所有元素不比父节点元素值小527136849圆形接点称为内节点圆形接点称为内节点, ,对应成功检索的数据元素对应成功检索的数据元素二分检索树的深度二分检索树的深度:二元比较树的深度二元比较树的深度: <11~22~33~44~55~66~77~88~9>9方形接点称为外节点方形接点称为外节点, ,对应不成功检索的数据子集对应不成功检索的数据子集n定理定理2.2 n 若若 n在在 区区 域域 [2k-1, 2k)中中 , 则则 对对 于于 一一 次次 成成 功功 的的 检检 索索 , BinSearch1至至多多作作k次次比比较较; 而而对对于于一一次次不不成成功功的的检检索索, 或或者者作作k-1次比较或者作次比较或者作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定理定理2.3 n 设设a[n]含有含有n(n≥1)个不同元素个不同元素, 排序为排序为a[1]<…

说明：说明：任何以比较为基础的检索算法任何以比较为基础的检索算法, 最坏情况下的比较次数都最坏情况下的比较次数都不可能低于不可能低于O(log n), 因此因此, 二分检索是最优的最坏情况算法二分检索是最优的最坏情况算法3. 以比较为基础检索的时间下界以比较为基础检索的时间下界n思考题：思考题：n n 1. 请证明请证明 E=I+2nn 2. 请证明请证明 S(n)=(I/n)+1n2.3 找最大和最小元素找最大和最小元素在在n个不同元素的集合个不同元素的集合a[n]中同时找出它的最大和最小元素中同时找出它的最大和最小元素.一、问题一、问题二、直接搜索二、直接搜索 StraitSearch(n, &max, &min){ *max=*min=a[0]; for(i=1; i*max) *max=a[i]; if(a[i]<*min) *min=a[i]; }} 比较次数：比较次数：2(n-1)将语句将语句1的体改写成的体改写成 if(a[i]>*max) *max=a[i]; else if(a[i]<*min) *min=a[i];最好情况：最好情况：最坏情况：最坏情况：平均情况：平均情况：n-12(n-1)3/2(n-1)由此可见由此可见, 直接搜索的时间复杂度为直接搜索的时间复杂度为:O(n)直接搜索的改进方法直接搜索的改进方法l三、实现分治的递归算法三、实现分治的递归算法 l 集合只有一个元素时集合只有一个元素时 *max=*min=a[i]；；l 集合只有两个元素时集合只有两个元素时 if(a[i]

再合并结果 递归算法递归算法typedef struct { ElemType max, min; } SOLUTION; SOLUTION MaxMin(i, j){ SOLUTION s, s1, s2; if(i==j) { s.max=s.min=a[i]; return s; } if(i==j-1) { if(a[i]=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(a[i]

2.4 分类分类一、问题一、问题l二、插入分二、插入分类类 基本思想基本思想已分已分类类的部分的部分未分未分类类的部分的部分a[1]…a[j-1]a[j]a[j+1]…a[n]InsertSort(int n){ for(j=1; j=0)&&(unsorted mid) while (h<=high) b[k++]=a[h++]; /* 转储剩余部分 */ else while(l<=mid) b[k++]=a[l++]; a[low : high]=b[low : high]; /* 将b数组转储到a */ }已分类子集的归并算法已分类子集的归并算法 时间复杂度时间复杂度 缺点与改进缺点与改进结合插入分类与归并分类各自的优点结合插入分类与归并分类各自的优点l四、快速分类四、快速分类 设计思路设计思路a[1]…a[j-1]a[j]a[j+1]…a[n]使使a[1:j-1]≤a[j]a[j]使使a[j+1:n]≥a[j]对对a[1:j-1]快速分快速分类类a[j]对对a[j+1:n] 快速分快速分类类已分已分类类的集合的集合 实现部分分类的划分过程举例实现部分分类的划分过程举例原始41362578指针r=4jk一次循 环r=4jkr=41326578二 次循 环kj交换位 置213r=46578返回交换位置 k 实现部分分类的划分算法实现部分分类的划分算法 Partition (p, q){ r=a[p]; j=p+1; k=q; while(1) { while ((j<=k) && (a[j]<=r)) j++; while ((j<=k) && (a[k]>=r)) k--; if (j

l一、问题一、问题2.5 选择选择 给定一个含给定一个含n个元素的集合个元素的集合a[n], 找出其中第找出其中第k小的元素，并将其小的元素，并将其转储到转储到a[k] 二、最直观的求解算法二、最直观的求解算法按非降次序分类按非降次序分类a[k]即为第即为第k小的元素小的元素完全分类做了不必要的运算，效率低完全分类做了不必要的运算，效率低l三、基于分治思想的选择算三、基于分治思想的选择算法法原始原始a[1]…a[j-1]a[j]a[j+1]…a[n]partition使使a[1:j-1]a[j]分治分治kj,在在a[j+1:n]中中选择选择基本思路基本思路用用partition算法实现分治算法实现分治nselection (p, q, k)n{ int j;n j=partition (p, q);n if (k==j) return;n if (k

符串，并将此递归算法改写成相应的迭代算法•递归的基本思路递归的基本思路——分治分治S为空字符串吗？为空字符串吗？按逆序输出除按逆序输出除S[0]外的子字符串外的子字符串输出输出S[0]返回返回YESNO递归算法递归算法void reverse (char * s){ if( *s!=’\0’ ) { reverse(s+1); putchar (*s); } return;}•输出输出s=”abc”的递归过的递归过程程进进入入递归调递归调用用, top=0递归调递归调用返回用返回, top=6顺顺序序条件条件栈栈中元素中元素top=, s= 顺顺序序条件条件addr, s 1*s=’a’stack[1]=s, (’a’)stack[2]=L2, (putchar)2, s+11top=6addr=stack[6]s=stack[5]2*s=’b’stack[3]=s, (’b’)stack[4]=L2 , (putchar)4, s+22top=4addr=stack[4]s=stack[3]3*s=’c’stack[5]=s, (’c’)stack[6]=L2 , (putchar)6, s+33top=2addr=stack[2]s=stack[1]4*s=’\0’调调用用结结束，束，转转返回返回处处理理4top=0完全返回完全返回nvoid reverse (char * s)n{ extern ElemType stack[2*n+1], top=0;n L1: n if( *s!=’\0’ )n { stack[++top]=s; stack[++top]=L2; s=s+1;n goto L1;n L2: n putchar(*s);n } // 接下来处理返回语句n if(top==0 ) return; // 栈为空n elsen { addr=stack[top--]; // 恢复地址n s=stack[top--]; // 恢复参数n if(addr == L2) goto L2;n }n}改写的迭代算法改写的迭代算法nvoid reverse(char * s)n{ int top=0;n while(*s!=’\0’) n { top++; n s++; n }n while (top!=0)n { putchar(*s);n s--; top--;n }n} 优化后的迭代算法优化后的迭代算法n 例例2：写一个求数组：写一个求数组a[n]中的最大元素的递归算法并将其改写中的最大元素的递归算法并将其改写成迭代算法。

成迭代算法a[i] a[i+1] … a[n-1] 分治的思路分治的思路:int max (int i){ int j=i, k; if(ia[j]) k=i; else k=j; } else k=n-1; return k;} 递归算法递归算法:(0) 开始，照搬（所有不涉及开始，照搬（所有不涉及递归调递归调用和返用和返回回语语句的代句的代码码都照搬）都照搬）(1) 定定义义和初始化堆和初始化堆栈栈(存存储储参数、局部参数、局部变变量、返回量、返回值值和返址和返址).int max(int i){ extern stack[4*n+1], top=0; int j=i, k;(2) 对对第一条可第一条可执执行行语语句定句定义标义标号号L1,每次每次递归调递归调用用执执行步行步骤骤 (3). (3) 将所有参数和局部将所有参数和局部变变量量进栈进栈. (4) 建立第建立第i个返回地址的个返回地址的标标号号Li，，进栈进栈. (5) 计计算本次算本次递归调递归调用用实实参的参的值值，并，并赋给赋给形形参参变变量量.(6) 无条件无条件转转移到移到L1进进入入递归递归. (7) 如果是如果是带带返回返回值值的的调调用，从用，从栈栈顶顶取回返取回返回回值值并代替并代替调调用，其余代用，其余代码码按原方式按原方式处处理，理，并将并将(4)建立的建立的标标号附于号附于该语该语句；如果是不句；如果是不带带返回返回值值的的调调用，用，则则将将(4)建立的建立的标标号直接号直接附于附于(6)对应对应的的语语句之后的那条句之后的那条语语句句. L1: if(i

移 if(top==0) return k; else { addr=stack[top--]; j=stack[top--]; i=stack[top--]; stack[++top]=k; if(addr==L2) goto L2; }}思考题：思考题： 为什么为什么k不作为局部变量在不作为局部变量在L1之后入栈，可否象之后入栈，可否象i, j一样处理？一样处理？nint max (int i)n{ int j, k=n-1;n for (j=n-2; j>=i; j--)n if (a[j]>a[k]) n k=j;n return k;n} 优化后的迭代算法优化后的迭代算法n 例例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 stack[5*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= stack[top--]; stack[++top]=p; stack[++top]=q; stack[++top]=m; stack[++top]=L3; p=m+1; q=q; goto L1; L3: s2=stack[top--]; s=combine(s1,s2); } if(top==0) return s； else { addr=stack[top--]; m=stack[top--]; q=stack[top--]; p=stack[top--]; stack[++top]=s; if(addr==L2) goto L2; else goto L3; }} 抽象控制迭代算法抽象控制迭代算法作业作业 设计、实现归并分类和快速分类算法，设计测试数据集，比较设计、实现归并分类和快速分类算法，设计测试数据集，比较二种分类算法的实际运行效率差异。

二种分类算法的实际运行效率差异 参考实验报告格式文件，提交设计报告的参考实验报告格式文件，提交设计报告的A4打印稿打印稿, 由班干部由班干部收集后统一提交，不单独受理收集后统一提交，不单独受理。