算法设计与分析课件

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,*,*,2024/8/8,第,2,部分 算法设计策略,第,5,章 分治法,2023/8/20第2部分 算法设计策略第5章 分治法,2024/8/8,5.2,求最大最小元,5.1,分治法的基本思想,5.3,二分搜索,5.4,排序问题,5.5,选择问题,5.6,斯特拉森矩阵乘法,2023/8/205.2 求最大最小元,2024/8/8,5.2,求最大最小元,2023/8/205.2 求最大最小元,2024/8/8,问题,在一个元素集合,L,中寻找最大元素和最小元素的问题。,一般方法？,2023/8/20 问题,2024/8/8,5.2.1,分治法求解,【,程序,5,4】,求最大最小元,template,void SortableList:MaxMin(T&max,T&min)const,if(n=0)return;,max=min=l0;,for(int i=1;imax)max=li;,if(limin)min=li;,时间复杂度？,2023/8/205.2.1 分治法求解【程序54】求,2024/8/8,【,程序,5,5】,分治法求最大最小元,template,void SortableList:MaxMin(int i,int j,T&max,T&min)const,T min1,max1;,if(i=j)max=min=li;,else if(i=j-1)/,只有两个元素时,if(lilj),max=lj;min=li;,else,max=li;min=lj;,2023/8/20【程序55】分治法求最大最小元,2024/8/8,else,int m=(i+j)/2;,MaxMin(i,m,max,min);,MaxMin(m+1,j,max1,min1);,if(maxmin1)min=min1;,2023/8/20 else,2024/8/8,5.2.2,时间分析,定理,5,2,设有,n,个元素的表，假定,n,是,2,的幂，即,n=2,k,，,k,是正整数，程序,5,5,在最好、平均和最坏情况下的比较次数都为,3n/22,。,设,n=2,k,，易解,2023/8/205.2.2 时间分析定理52 设n=2,2024/8/8,5.1,一般方法,2023/8/205.1 一般方法,2024/8/8,5.1.1,分治法的基本思想,分治法,顾名思义就是分而治之。一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；第二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成原问题的解。由于分治法要求分解成同类子问题，并允许不断分解，使问题规模逐步减小，最终可用已知的方法求解足够小的问题，因此，分治法求解很自然导致一个递归算法。,2023/8/205.1.1 分治法的基本思想 分治法顾名,2024/8/8,【,程序,5-1】,分治法,SolutionType DandC(ProblemType P),ProblemType P,1,，,P,2,，,，,P,k,;,if(Small(P)return S(P);else,Divide(P,，,P,1,，,P,2,，,，,P,k,);Return Combine(DandC(P,1,),，,DandC(P,2,),，,，,DandC(P,k,);,2023/8/20【程序5-1】分治法,2024/8/8,【,程序,5-2】,一分为二的分治法,SolutionType DandC(int left,，,int right),if(Small(left,right),return S(left,right);,else,int m=Divide(left,，,right);Return Combine(DandC(left,，,m),，,DandC(m+1,，,right);,2023/8/20【程序5-2】一分为二的分治法,2024/8/8,5.1.2,算法分析,采用分治法求解问题通常得到一个递归算法。如果较大的问题被分解成同样大小的几部分，那么分析相应算法的执行时间，往往可得到如下的递推关系式：,T,(,n,)=,aT,(,n,/,b,)+,cn,k,，,T,(1)=,c,2023/8/205.1.2 算法分析 采用分治法求解问,2024/8/8,定理,5-1,设,a,b,c,和,k,为常数，,T(n)=aT(n/b)+cn,k,，,T(1)=c,，则，,2023/8/20定理5-1 设a,b,c和k为常数，T,2024/8/8,n=b,m,2023/8/20n=bm,2024/8/8,设,r=b,k,/a,，下面分三种情况计算。,（,1,）若,r1,，则,所以,2023/8/20设r=bk/a，下面分三种情况计算,2024/8/8,5.1.3,排序问题 数据结构,【,程序,5,3】,可排序表类,template,struct E,/,可排序表中元素的类型,operator K()const return key;,K key;,D data;,;,2023/8/205.1.3 排序问题 数据结构【程,2024/8/8,template,class SortableList,/,可排序表类,public:,SortableList(int mSize);,SortableList();,private:,T*l;/,指向动态生成的一位数组,int maxSize;,int n;,;,2023/8/20template,2024/8/8,5.3,二分搜索,2023/8/205.3 二分搜索,问题,在有序表（已按关键字值非减排序）中搜索给定元素的问题。,a,0,a,0,a,m-1,a,m,a,m+1,a,n-2,a,n-1,2024/8/8,问题a0a0am-1amam+1an-2an-12023,2024/8/8,5.3.1,分治法求解,int SortableList:BSearch(const T&x,int left,int right)const,说明,:,在范围为,left,right,的表中搜索与,x,有相同关键字值的元素；如果存在该元素，则函数返回该元素在表中的位置，否则函数返回,1,，表示搜索失败。,2023/8/205.3.1 分治法求解int Sorta,2024/8/8,【,程序,5,6】,二分搜索算法框架,template,int SortableList:BSearch(const T&x,int left,int right)const,if (left=right),int m=Divide(left+right);,if(xlm),return BSearch(x,m+1,right);,else return m;,return-1;,2023/8/20【程序56】二分搜索算法框架,2024/8/8,5.3.2,对半搜索,对半搜索,对半搜索是一种二分搜索。设当前搜索的子表,为（,a,left,a,left+1,a,right,），,令,m=(left+right)/2,2023/8/205.3.2 对半搜索 对半搜索,2024/8/8,【,程序,5,7】,对半搜索递归算法,template,int SortableList:BSearch(const T&x,int left,int right)const,if (left=right),int m=(left+right)/2;,if(xlm),return BSearch(x,m+1,right);,else return m;,return-1;,2023/8/20【程序57】对半搜索递归算法,2024/8/8,定理,5,3,对于,n,0,，程序,5,7,的对半搜索递归函数,BSearch,是正确的。,程序,5-7,是尾递归函数，易改为迭代形式,参考程序,5-8,2023/8/20定理53,2024/8/8,/,程序,5-8,：对半搜索的迭代算法,template,int SortableList:BSearch1(const T&x)const,int m,left=0,right=n-1;,while (left=right),m=(left+right)/2;,if(xlm)left=m+1;,else return m;/,搜索成功,return-1;/,搜索失败,2023/8/20/程序5-8：对半搜索的迭代算法,2024/8/8,5.3.3,二叉判定树,二分搜索过程的算法行为可以用一棵二叉树来描述。通常称这棵描述搜索算法执行过程的二叉树为,二叉判定树,(binary decision tree),。,2023/8/205.3.3 二叉判定树 二分搜索过程的,2024/8/8,如何构建二叉判定树,内节点,外节点,2023/8/20如何构建二叉判定树内节点外节点,2024/8/8,性质,5,1,具有,n,个内结点的对半搜索二叉判定树的左子树上有,(n-1)/2,个内结点，右子树上有,n/2,个内结点。,性质,5,2,具有,n(n0,）个内结点的二叉判定树的高度为,log n,+1,（不计外结点）。,2023/8/20性质 51,2024/8/8,性质,5,3,若,n=,2,h,-1,，则对半搜索二叉判定树是满二叉树。,性质,5,4,若,n=,2,h,-1,，则对半搜索二叉判定树的外结点均在,h+1,层上，否则，在第,h,或,h+1,层上，,h=,log n,+1,。,2023/8/20性质 53,2024/8/8,定理,5,4,对半搜索算法在成功搜索的情况下，关键字值之间的比较次数不超过,log n,+1,。对于不成功的搜索，算法需要作,log n,或,log n,+1,次比较。,定理,5,5,对半搜索算法在搜索成功时的平均时间复杂度为,(log n),。,对半搜索是一个最优算法,2023/8/20定理 54 对半搜索是一个最优算法,2024/8/8,5.3.4,搜索算法的时间下界,定理,5,6,在一个有,n,个元素的集合中，通过关键字值之间的比较，搜索指定关键字值的元素，任意这样的算法在最坏情况下至少需要作,log,n,+1,次比较。,2023/8/205.3.4 搜索算法的时间下界 定理56,2024/8/8,练习,1,编写程序实现三分搜索算法，分析其时间复杂度，并与对半搜索算法的时间性能进行比较。,2023/8/20练习1编写程序实现三分搜索算法，分析其时间,2024/8/8,5.4,排序问题,2023/8/205.4 排序问题,2024/8/8,问题,排序是将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。,2023/8/20 问题,2024/8/8,5.4.1,合并排序,合并两个有序序列,两路合并排序的基本运算是把两个有序序列合并成一个有序序列。,2023/8/205.4.1 合并排序 合并两个有序序列,2024/8/8,【,程序,5,9】Merge,函数,template,void SortableList:Merge(int left,int mid,int right),T*temp=new Tright-left+1;,int i=left,j=mid+1,k=0;,while(i=mid)&(j=right),if(li=lj)tempk+=li+;,else tempk+=lj+;,while(i=mid)tempk+=li+;,while(j=right)tempk+=lj+;,for(i=0,k=left;k=right;)lk+=tempi+;,时间复杂度分析？,2023/8/20【程序59】Merge函数时间复杂度分,2024/8/8,2023/8/20,2024/8/8,分治法求解,将待排序的元素序列一分为二分，得到两个长度基本相等的子序列；,然后对两个子序列分别排序，如果子序列较长，还可继续细分，直到子序列的长度不超过,1,为止；,当分解所得的子序列已排列有序，可以将两个有序子序列，合并成一个有序子序列,-,合并排序,2023/8/20 分治法求解-合并排序,2024/8/8,【,程序,5,10】,两路,合并排序,template,void SortableList:MergeSort(int left,int right),if(leftright),int mid=(left+right)/2;,MergeSort(left,mid);,MergeSort(mid+1,right);,Merge(left,mid,right);,2023/8/20【程序510】两路合并排序,2024/8/8,template,void SortableList:MergeSort(),MergeSort(0,n-1);,2023/8/20template,2024/8/8,2023/8/20,2024/8/8,性能分析,合并排序递归算法的时间复杂度为,O(n log,n),。,2023/8/20 性能分析,2024/8/8,5.4.2,快速排序,快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是：,在待排序的序列,(K,0,K,1,K,n-1,),中选择一个元素作为分划元素，也称为,主元,（,pivot,）。不妨假定选择,K,为主元。经过一趟特殊的分划处理将原序列中的元素重新排列，使得以主元为轴心，将序列,分成左右两个子序列,。主元左测子序列中所有元素都不大于主元，主元右测子序列中所有元素都大于主元。,2023/8/205.4.2 快速排序快速排序采用一种特,2024/8/8,分划操作,2023/8/20 分划操作,2024/8/8,【,程序,5,11】,分划函数,template,int SortableList:,Partition(int left,int right),/,前置条件：,left,right,int i=left,j=right+1;,/,初始主元放在最左边,do,do i+;while(lilleft);,if(ij)Swap(i,j);,/,交换,while(ij);,Swap(left,j);,/,主元作为分界线,return j;,/,返回主元位置,2023/8/20【程序511】分划函数,2024/8/8,快速排序算法,2023/8/20快速排序算法,2024/8/8,【,程序,5,12】,快速排序,template,void SortableList:QuickSort(),QuickSort(0,n-1);,template,void SortableList:,QuickSort(int left,int right),if(leftright),int j=Partition(left,right);,QuickSort(left,j-1);,QuickSort(j+1,right);,2023/8/20【程序512】快速排序,2024/8/8,时间分析,存在的最坏情况,存在的最好情况,最坏情况时间,W(n),W(n-1)+n+1,W(n-2)+(n+1)+n,W(1)+(n+1)+,+3,=O(n,2,),2023/8/20 时间分析,2024/8/8,平均情况时间,2023/8/20平均情况时间,2024/8/8,2023/8/20,2024/8/8,5.4.3,排序算法的时间下界,定理,5,7,任何一个通过关键字值比较对,n,个元素进行排序的算法，在最坏情况下，至少需作（,n/4,）,log,n,次比较。,2023/8/205.4.3 排序算法的时间下界定理 5,合并排序与快速排序比较,1.,基本思想,2.,划分与组合方法的区别,3.,时间复杂度,2024/8/8,合并排序与快速排序比较1.基本思想2023/8/20,2024/8/8,5.5,选择问题,2023/8/205.5 选择问题,2024/8/8,问题,选择问题（,select problem,）是指在,n,个元素的集合中，选出某个元素值大小在集合中处于第,k,位的元素，即所谓的,求第,k,小元素问题,(kth-smallest),。,2023/8/20问题,2024/8/8,5.5.1,分治法求解,设原表长度为,n,，假定经过一趟分划，分成两个左右子表，其中左子表是主元及其左边元素的子表，设其长度为,p,，右子表是主元右边元素的子表。那么，若,k=p,，则主元就是第,k,小元素；否则若,kp,，则第,k,小元素必定在右子表中，需求解的子问题成为在右子表中求第,k-p,小元素。,2023/8/205.5.1 分治法求解 设原表长度为n，,2024/8/8,5.5.2,随机选择主元,随机选主元算法,假定表中,元素各不相同,，并且随机选择主元，即在下标区间,left,right,中随机选择一个下标,r,，以该下标处的元素为主元。,2023/8/205.5.2 随机选择主元 随机选主元算法,2024/8/8,【,程序,5,13】,Select,函数 ，元素集合为,l,template,ResultCode SortableList:Select1(T&x,int k),/,在,l,中找到第,k,大元素，通过,x,返回,if(nn|k=0)return OutOfBounds;,int left=0,right=n;ln=INFTY;,do,int j=rand()%(right-left+1)+left;,/,确定主元,Swap(left,j);,j=Partition(left,right);/,划分,if(k=j+1)x=lj;return Success;,else if(kj+1)right=j;,else left=j+1;,while(true);,2023/8/20【程序513】Select函数 ，元,2024/8/8,定理,5,8,程序,5,13,的,Select,算法的平均时间,A(n)=O(n),。,算法的最坏情况时间复杂度,O(n,2,),，？,。,2023/8/20定理58,2024/8/8,5.5.3,线性时间选择算法,改进的选择算法采用,二次取中法,(median of medians rule),确定主元,2023/8/205.5.3 线性时间选择算法改进的选择算,2024/8/8,2023/8/20,2024/8/8,【,程序,5,14】,线性时间选择算法,ResultCode SortableList:Select(T&x,int k),if(nn|k=0),return OutOfBounds;,int j=Select(k,0,n-1,5);,x=lj;return Success;,2023/8/20【程序514】线性时间选择算法,2024/8/8,template,int SortableList:Select(int k,int left,int right,int r),/,对,leftright,范围内的元素分组，每组,r,个元素采用二次取中法，确定主元,int n=right-left+1;,if(n=r),InsertSort(left,right);,/,直接排序,return left+k-1;,2023/8/20template,2024/8/8,for(int i=1;i=n/r;i+),InsertSort(left+(i-1)*r,left+i*r-1);,/,对每组元素直接排序,Swap(left+i-1,left+(i-1)*r+Ceil(r,2)-1);,int j=Select(Ceil(n/r,2),left,left+(n/r)-1,r);,/,定主元,Swap(left,j);,j=Partition(left,right);,/,划分,if(k=j-left+1)return j;,else if(kj-left+1)return Select(k,left,j-1,r);,else return Select(k-(j-left+1),j+1,right,r);,2023/8/20 for(int i=1;i=n,2024/8/8,5.5.4,时间分析,以二次取中的中间值,mm,为主元，经过一趟分划，左、右两个子表的大小均至多为：,n,n/r,/2,r/2,设,T(n),为当表长为,n,时执行程序,5,14,所需的时间。,T(n),由三部分时间组成：,T(n),T(,n/5,)+T(3n/4)+cn,用归纳法容易证明，,T(n),20cn,，,n,1,是线性时间的。,2023/8/205.5.4 时间分析 以二次取中的中间值m,2024/8/8,5.5.5,允许重复元素的选择算法,由于允许包含相同元素，左子表中除了小于,mm,的元素外，还包含与,mm,相同值的元素。因此，左子表的大小至多可达,n,n/r,/2,r/2,+1/2,n/r,/2,r/2,=n-1/2,n/r,/2,r/2,容易用归纳法证明对于所有,n,90,，,T(n),T(n/9)+T(7n/8)+cn,72cn,，,n,90,2023/8/205.5.5 允许重复元素的选择算法由于允,2024/8/8,5.6,斯特拉森矩阵乘法,2023/8/205.6 斯特拉森矩阵乘法,2024/8/8,问题,矩阵相乘,C=A x B,2023/8/20问题,2024/8/8,5.6.1,分治法求解,C,11,A,11,B,11,+A,12,B,21,C,12,A,11,B,12,+A,12,B,22,C,21,A,21,B,11,+A,22,B,21,C,22,A,21,B,12,+A,22,B,22,T(n)=,(n,3,),2023/8/205.6.1 分治法求解 C11A11B1,2024/8/8,5.6.2,斯特拉森分治法,P=(A,11,+A,22,)(B,11,+B,22,),Q=(A,21,+A,22,)B,11,R=A,11,(B,12,-B,22,),S=A,21,(B,21,-B,11,),T=(A,11,+A,12,)B,22,U=(A,21,-A,11,)(B,11,+B,12,),V=(A,12,-A,22,)(B,21,+B,22,),2023/8/205.6.2 斯特拉森分治法P=(A11+,2024/8/8,C,11,=P+S-T+V,C,12,=R+T,C,21,=Q+S,C,22,=P+R-Q+U,T(n,)=,(n,log 7,),(n,2.81,),2023/8/20C11=P+S-T+VT(n)=(nl,2024/8/8,练习,2,设计算法解决大数相乘问题（长为,n,位的两个,2,进制数相乘）使其算法复杂度低于,n,2,。,2023/8/20练习2设计算法解决大数相乘问题（长为n位的,