[理学]《算法设计与分析》第05章课件(PPT 103页)

1、算法设计与分析DeSign and Analysis of AlgorithmsIn C+“十一五”国家级规划教材 陈慧南 编著电子工业出版社第1页，共103页。第2部分 算法设计策略第2页，共103页。第5章 分治法 第3页，共103页。5.1 分治法的基本思想 5.2 求最大最小元 5.3 二分搜索 5.4 排序问题5.5 选择问题5.6 斯特拉森矩阵乘法 第4页，共103页。5.1 一般方法 第5页，共103页。5.1.1 分治法的基本思想 分治法顾名思义就是分而治之。一个问题能够用分治法求解的要素是：第一，问题能够按照某种方式分解成若干个规模较小、相互独立且与原问题类型相同的子问题；第

2、二，子问题足够小时可以直接求解；第三，能够将子问题的解组合成原问题的解。由于分治法要求分解成同类子问题，并允许不断分解，使问题规模逐步减小，最终可用已知的方法求解足够小的问题，因此，分治法求解很自然导致一个递归算法。 第6页，共103页。【程序5-1】 分治法SolutionType DandC(ProblemType P)ProblemType P1，P2，Pk;if (Small(P) return S(P);else Divide(P，P1，P2，Pk);Return Combine(DandC(P1)， DandC(P2)，DandC(Pk); 第7页，共103页。【程序5-2】 一分

3、为二的分治法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); 第8页，共103页。5.1.2 算法分析 采用分治法求解问题通常得到一个递归算法。如果较大的问题被分解成同样大小的几部分，那么分析相应算法的执行时间，往往可得到如下的递推关系式：T(n) = aT(n/b) + cnk，T(1) = c 第9页，共103页。定理5-

4、1 设a,b,c和k为常数，T(n)=aT(n/b)+cnk，T(1)=c，则， 第10页，共103页。第11页，共103页。设r= bk /a ，下面分三种情况计算 。（1）若r1，则 所以 第12页，共103页。例如：(1) T(n)=2T(n/2)+n a=2,b=2,k=1,a=bk 所以 T(n)= (nlog(n) (2) T(n)=4T(n/4)+n2 a=4,b=4,k=2,abk 所以 T(n)= (n4)第13页，共103页。5.1.3 数据结构 【程序53】 可排序表类template struct E /可排序表中元素的类型operator K( ) const ret

5、urn key;/重载类型转换运算符K key;/关键字可以比较大小D data;/其他数据;第14页，共103页。 template class SortableList /可排序表类 public:SortableList(int mSize)/构造函数 maxSize=mSize;l=new TmaxSize;n=0;SortableList()delete l;/析构函数 private: T *l ;/定义动态一维数组int maxSize;/线性表的最大表长int n;/线性表的实际长度; 第15页，共103页。5.2 求最大最小元 第16页，共103页。 问题在一个元素集合中寻找

6、最大元素和最小元素的问题。第17页，共103页。5.2.1 分治法求解【程序54】 求最大最小元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; / /Tn=2(n-1) 第18页，共103页。5.2.1 分治法求解【程序54】 求最大最小元template void SortableList:MaxMin(T& max, T& min)const if (n=0)return; max

7、=min=l0; for (int i=1; imax) max=li; else if(limin) min=li; Wn=2(n-1) (递减有序） Bn=n-1(递增有序）第19页，共103页。【程序55】分治法求最大最小元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; 第20页，共103页。 else in

8、t m=(i+j)/2; MaxMin(i,m,max,min); MaxMin(m+1,j,max1,min1); if (maxmin1) min=min1; 第21页，共103页。5.2.2 时间分析定理52 设有n个元素的表，假定n是2的幂，即n=2k，k是正整数，程序55在最好、平均和最坏情况下的比较次数都为3n/22。第22页，共103页。n=2k,T(n)=2T(n/2)+2T(n)=3n/2-2第23页，共103页。5.3 二分搜索第24页，共103页。问题在有序表（已按关键字值非减排序）中搜索给定元素的问题。第25页，共103页。5.3.1 分治法求解int Sortable

9、List:BSearch(const T& x, int left,int right)const后置条件: 在范围为left,right的表中搜索与x有相同关键字值的元素；如果存在该元素，则函数返回该元素在表中的位置，否则函数返回1，表示搜索失败。第26页，共103页。二分搜索1.二分搜索的基本思想二分搜索的基本思想是：首先将待查值x与有序表l0到ln-1的中的下标为mid上的元素进行比较，若相等，则查找成功；否则，若xlmid，则在lmid+1到ln-1中继续查找。第27页，共103页。每通过一次关键字的比较，搜索区间的长度就缩小一次，如此不断进行下去，直到找到值等于x的元素；若当前的查找

10、区间为空,表示查找失败。从上述查找思想可知，每进行一次关键字比较，都将原区间一分为二，故称为二分搜索。如果把要搜索区间的长度缩小一半，就称为对半搜索。第28页，共103页。【程序56】二分搜索算法框架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; 第29页，共103页。5.3.2 对半搜索 对

11、半搜索 对半搜索是一种二分搜索。设当前搜索的子表 为（aleft,aleft+1,aright）， 令 m=(left+right)/2 第30页，共103页。例如，假设给定有序表中关键字为8,17,25,44,68,77,98,100,115,125，将查找K=17和K=120的情况描述为以下形式。第31页，共103页。第32页，共103页。第33页，共103页。第34页，共103页。【程序57】 对半搜索递归算法template int SortableList:BSearch(const T& x, int left, int right)const if (left=right) in

12、t m=(left+right)/2; if (xlm) return BSearch(x,m+1,right); else return m; return -1; 第35页，共103页。二分查找的性能分析 为了分析二分查找的性能，可以用二叉树来描述二分查找过程。把当前查找区间的中点作为根结点，左子区间和右子区间分别作为根的左子树和右子树，左子区间和右子区间再按类似的方法，由此得到的二叉树称为二分查找的判定树。例如，对关键字序列8,17,25,44,68,77,98,100,115,125，的判定树下图。第36页，共103页。二分查找的性能分析 查找成功：最好：Ws=1；最坏：Ws= log

13、n +1= O(logn)查找失败：Wf= logn +1 = (logn)第37页，共103页。搜索成功的平均时间复杂度：从上图可知，查找根结点68，需一次查找，查找17和100，各需二次查找，查找8、25、77、115各需三次查找，查找44、98、125各需四次查找。于是，可以得到结论：二叉树第K层结点的查找次数各为k次(根结点为第1层)，而第k层结点数最多为2k-1个。假设该二叉树的深度为h， 则二分查找的成功的平均查找次数为（假设每个结点的查找概率相等）：第38页，共103页。ASL= = 1/n 1/n(1+22+322+h2h-1) =1/n设s= =20+221+322+(h-1

14、)2h-2+h2h-1则2s=21+222+(h-2)2h-2+(h-1)2h-1+h2hs=2s-s=h .2h-(20+21+22+2h-2+2h-1) =h .2h-(2h-1) 第39页，共103页。ASL=1/n( log2(n+1) (2h-1+1)-n) =1/n( log2(n+1) (n+1)-n) =(n+1)/n log2(n+1)-1 =(1+1/n) log2(n+1)-1当n很大时，ASL log2(n+1)-1 可以作为二分查找成功时的平均查找长度，它的时间复杂度为 (log2n)。 根据二叉树的性质，最大的结点数n=2h-1，h=log2(n+1) ，于是可以得

15、到平均查找次数ASL=s/nASL= 1/n(h2h-(2h-1)第40页，共103页。5.3.4 搜索算法的时间下界 定理56 在一个有n个元素的集合中，通过关键字值之间的比较，搜索指定关键字值的元素，任意这样的算法在最坏情况下至少需要作log n+1次比较。第41页，共103页。5.4 排序问题 第42页，共103页。 问题 排序是将一个元素序列调整为按指定关键字值的递增（或递减）次序排列的有序序列。 第43页，共103页。合并两个有序表：合并算法排序也属于分治方法。合并（Merge）就是将两个或多个有序表合并成一个有序表，例如下图所示的两个有序表经合并运算后得到一个有序表。我们在此只用到

16、两个有序表的合并，称为二路合并Two-way merge）。5.4.1 合并排序第44页，共103页。合并排序（Merge sort）就是利用这种合并过程进行排序，即先将n个数据看成n个长度为l的表，将相邻的表成对合并，得到长度为2的n/2个有序表；进一步再将相邻表成对合并，得到长度为4的n/4个有序表；如此重复做下去，直至所有数据均合并到一个长度为n的有序表为止，即完成排序。上述每一次的合并过程称为一趟Pass），整个排序过程叫二路合并排序。下图是二路合并排序过程的一个例子。合并排序第45页，共103页。7 15 13 10 4 20 19 87 15 10 13 4 20 8 197 15

17、 13 10 4 20 19 8 7 10 13 15 4 8 19 20 4 7 8 10 13 15 19 20第46页，共103页。合并两个有序序列第47页，共103页。【程序59】 合并两个有序序列（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

18、=mid) tempk+=li+; while (j=right) tempk+=lj+; for (i=0,k=left;k=right;) lk+ = tempi+; 第48页，共103页。 分治法求解 将待排序的元素序列一分为二分，得到两个长度基本相等的子序列，如同对半搜索的做法；然后对两个子序列分别排序，如果子序列较长，还可继续细分，直到子序列的长度不超过1为止；当分解所得的子序列已排列有序，可以采用上面介绍的将两个有序子序列，合并成一个有序子序列的方法，实现将子问题的解组合成原问题解，这是分治法不可缺少的一步。第49页，共103页。 对于二路合并，如果数据个数n是2的整数次方，则所需

19、的趟数为logn，例如n=8，logn=3，故共需三趟合并过程。如果n不是2的整数次方，则在每趟合并时表的数目不一定总是偶数个。若表的数目为奇数，就剩下一个表要“轮空”，直接进入下一趟。这样，下一趟合并时此表的长度与其它的表将不相同，因此我们设计的合并过程，并不要求待合并的两个表长度必须相同。 第50页，共103页。【程序510】两路合并排序template void SortableList:MergeSort(int left,int right) if (leftright) int mid = (left+right)/2; MergeSort(left,mid); MergeSort

20、(mid+1,right); Merge(left,mid,right); template void SortableList:MergeSort() MergeSort(0,n-1);第51页，共103页。第52页，共103页。 性能分析合并排序递归算法的时间复杂度为 (nlog n)。定理5-1 设a,b,c和k为常数，T(n)=aT(n/b)+cnk，T(1)=c，则， 第53页，共103页。使用递归树可以形象地看到递推式的迭代过程。 例2-13 T(n) = 2T(n/2) + n的递归树递归路径：n-(1/2)n-(1/2)2n.(1/2)kn1(1/2)kn=1，即n/2k=1，

21、即2k=n，k=log2n=logn所以 T(n)=n*(logn+1)= (nlogn)第54页，共103页。5.4.2 快速排序快速排序采用一种特殊的分划操作对排序问题进行分解，其分解方法是：在待排序的序列(K0,K1,Kn-1)中选择一个元素作为分划元素，也称为主元（pivot）。不妨假定选择K为主元。经过一趟特殊的分划处理将原序列中的元素重新排列，使得以主元为轴心，将序列分成左右两个子序列。主元左测子序列中所有元素都不大于主元，主元右测子序列中所有元素都不小于主元。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20第55页，共103页。1、主元最后的位置

22、就是它最终的合适位置，进一步的运算过程中此数据即不必再动；2、以后的排序运算只需在划分成的两部分里进行，两部分之间不会再有数据互换。3、第一次划分以后，再用相同的算法对划成的部分进行类似的运算，即从每部分中任选一个数据将其划分成更小的两部分，依此递归地做下去，直至每个小部分中的数据个数均不超过一个为止，排序过程即结束。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20第56页，共103页。 分划操作第57页，共103页。【程序511】 分划函数template int SortableList:Partition(int left, int right) /前置

23、条件：leftright int i=left,j=right+1; do do i+; while (lilleft); if (ij) Swap(i,j); while (ij); Swap(left,j); return j; 第58页，共103页。快速排序算法第59页，共103页。【程序512】快速排序 template void SortableList:QuickSort() QuickSort(0,n-1);template void SortableList:QuickSort(int left,int right) if(leftright) int j=Partition(

24、left,right); QuickSort(left,j-1); QuickSort(j+1,right); 第60页，共103页。若快速排序出现最坏的情形（每次能划分成两个子区间，但其中一个是空），因此，快速排序的最坏时间复杂度为O(n2)。快速排序所占用的辅助空间为栈的深度，故最好的空间复杂度为O（logn），最坏的空间复杂度为O(n2)。若快速排序出现最好的情形（左、右子区间的长度大致相等），快速排序的最好时间复杂度应为O（nlog2n）。 时间分析理论上已经证明，快速排序的平均时间复杂度也为O（nlogn）。第61页，共103页。平均情况时间 第62页，共103页。第63页，共103

25、页。5.4.3 排序算法的时间下界定理 57 任何一个通过关键字值比较对n个元素进行排序的算法，在最坏情况下，至少需作（n/4）log n次比较。第64页，共103页。第65页，共103页。5.5 选择问题 第66页，共103页。问题选择问题（select problem）是指在n个元素的集合中，选出某个元素值大小在集合中处于第k位的元素，即所谓的求第k小元素问题(kth-smallest)。 第67页，共103页。5.5.1 分治法求解 设原表长度为n，假定经过一趟分划，分成两个左右子表，其中左子表是主元及其左边元素的子表，设其长度为p，右子表是主元右边元素的子表。那么，若k=p，则主元就是

26、第k小元素；否则若kp，则第k小元素必定在右子表中，需求解的子问题成为在右子表中求第k-p小元素。15 7 13 10 4 20 19 8 8 7 13 10 4 15 19 20第68页，共103页。5.5.2 随机选择主元 随机选主元算法 假定表中元素各不相同，并且随机选择主元，即在下标区间left,right中随机选择一个下标r，以该下标处的元素为主元。 第69页，共103页。 【程序513】Select函数template ResultCode SortableList:Select1(T& x,int k) if(nn|k=0) return OutOfBounds; int lef

27、t=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); 第70页，共103页。定理58 程序513的Select算法的平均时间A(n)=O(n)。算法的最坏情况时间复杂度O(n2) 。第71页，共103页。5.5.3 线性时间选择算法改进的选择算法采用二次取中法(median

28、of medians rule)确定主元 第72页，共103页。第73页，共103页。 【程序514】 线性时间选择算法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; 第74页，共103页。template int SortableList:Select(int k, int left,int right,int r) int n=right-left+1; if (n=r) InsertSort(left,

29、right); return left+k-1; 第75页，共103页。 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)

30、; else return Select(k-(j-left+1),j+1,right,r); 第76页，共103页。5.5.4 时间分析 以二次取中的中间值mm为主元，经过一趟分划，左、右两个子表的大小均至多为： nn/r/2 r/2 设T(n)为当表长为n时执行程序514所需的时间。T(n)由三部分时间组成： T(n)T(n/5)+T(3n/4)+cn 用归纳法容易证明，T(n)20cn，n1是线性时间的。 第77页，共103页。5.5.5 允许重复元素的选择算法由于允许包含相同元素，左子表中除了小于mm的元素外，还包含与mm相同值的元素。因此，左子表的大小至多可达 nn/r/2 r/2+

31、1/2 n/r/2 r/2 = n-1/2 n/r/2 r/2 容易用归纳法证明对于所有n90， T(n)T(n/9)+T(7n/8)+cn72cn，n90 第78页，共103页。5.6 斯特拉森矩阵乘法 第79页，共103页。问题 矩阵相乘 第80页，共103页。矩阵乘积的Strassen算法 C=AB=(cij)nn。 求C=AB即对n2个元素cij进行计算，故要作n3次乘法。相当时间内没有人怀疑过是否可以用少于n3次乘法来完成。其实不然，先以n=2的矩阵乘积为例。 对于矩阵第81页，共103页。则有：共需作8次乘法和4次加法。第82页，共103页。分治法求解大矩阵 C11A11B11+A

32、12B21C12A11B12+A12B22 C21A21B11+A22B21 C22A21B12+A22B22一个四阶方阵可以看作由4个二阶方阵组成第83页，共103页。分治法求解大矩阵 C11A11B11+A12B21C12A11B12+A12B22 C21A21B11+A22B21 C22A21B12+A22B22一个n阶方阵可以看作由4个n/2阶的方阵组成，二个n阶方阵的乘积，转化为八个n/2阶方阵的乘积和4个n/2阶方阵的加法。T(n)=(n3) 第84页，共103页。定理5-1 设a,b,c和k为常数，T(n)=aT(n/b)+cnk，T(1)=c，则， 第85页，共103页。5.6

33、.2 斯特拉森分治法P=(A11+A22)(B11+B22)Q=(A21+A22)B11R=A11(B12-B22)S=A21(B21-B11)T=(A11+A12)B22U=(A21-A11)(B11+B12)V=(A12-A22)(B21+B22)第86页，共103页。C11=P+S-T+VC12=R+TC21=Q+SC22=P+R-Q+UT(n)= (nlog 7)(n2. 81) 第87页，共103页。2*2矩阵的最少乘法次数是7。目前最好的矩阵乘法的时间上界是：O(n2.376)。第88页，共103页。我们研究两个n位二进制数相乘的问题。用普通的方法运算，将乘数的每一位（由低位至高位）逐个去乘被乘数，每乘一次将乘积与原来的积相加，然后乘数和乘积移位一步，如此下去直至乘数的最高位运算完即得出结果，这样运算共需n2 次一位乘一位运算，n(n-1)次一位加一位运算和n次移位，假设两个一位数相乘，两个一位数相加和任何数移位一步所需运算