算法分析与设计第四章3(分治法快速分类)课件.ppt

1、2008-09-01版权所有：杨波，武汉科技大学理学院 第四章第四章 分治法分治法2008-09-01版权所有：杨波，武汉科技大学理学院 4.5 4.5 快速分类快速分类1.划分与快速分类n 快速分类是一种基于划分的分类方法；n 划分：选取待分类集合A中的某个元素t，按照与t的大小关系重 新整理A中元素，使得整理后t被置于序列的某位置上，而序列中所有在t以前出现的元素均小于等于t，而所有出 现在t以后的元素均大于等于t。这一元素的整理过程称为 划分（Partitioning）。元素t称为划分元素。n 快速分类：通过反复地对待排序集合进行划分达到分类目的的分类算法。2008-09-01版权所有：

2、杨波，武汉科技大学理学院 快速分类的基本思想快速分类的基本思想 对于输入的子数组am:p-1，按以下3个步骤进行排序：n分解（divide）：以am为基准元素（假定第一个元素am是划分元素）将am:p-1分成3段am:q-1，aq和aq+1:p-1，使得am:q-1中任何元素小于等于aq，aq+1:p-1中任何元素大于等于aq，下标q 在划分过程中确定。n递归求解（conquer）：通过递归调用快速排序算法，分别对am:q-1和aq+1:p-1进行排序。n合并（merge）：由于对 am:q-1和aq+1:p-1的排序是就地进行的，所以在am:q-1和aq+1:p-1都已排好序后不需要执行任何

3、计算，am:p-1就已排好序。2008-09-01版权所有：杨波，武汉科技大学理学院 划分过程的算法描述划分过程的算法描述public static int Partition(int m,int p)/在am，am+1，ap-1中的元素按如下方式重新排列：如果最初t=am，则在重排完成之后，/对于m和p-1之间的某个q，有aq=t，并使得对于mkq，有ak t，而对于qkp，有ak t。/退出时返回值为划分元素所在的下标位置 int i,v;/v为划分元素，i为从左到右计数，p从右到左计数 v=am;i=m+1;p=p-1;int temp;/临时交换单元 while(true)while(

4、aiv)p-;/直到不大于v,p向左移动 if(ip)/ai与ap交换位置 temp=ai;ai=ap;ap=temp;else break;am=ap;ap=v;/划分元素在位置p return p;ap被定义，但为一限界值apam，不包含在实际的分类区间内。(技巧技巧：假如是按照从大到小排列，经过Partition算法之后进行从小到大排列，引入ap则程序易于实现）算法对集合am:p-1进行划分元素am作为划分元素2008-09-01版权所有：杨波，武汉科技大学理学院 划分实例（划分实例（1次划分）次划分）12345678910iP65 70 75 80 85 60 55 50 45 100

5、00 2965 45 75 80 85 60 55 50 70 10000 3865 45 50 80 85 60 55 75 70 10000 4765 45 50 55 85 60 80 75 70 10000 5665 45 50 55 60 85 80 75 70 10000 6560 45 50 55 65 85 80 75 70 100005Partition(m,p)=Partition(1,10)划分元素p=52008-09-01版权所有：杨波，武汉科技大学理学院 经过一次“划分”后，实现了对集合元素的调整：以划分元素为界，左边子集合的所有元素均小于等于右边子集合的所有元素。按

6、同样的策略对两个子集合进行分类处理。当子集合分类完毕后，整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类方法称为快速分类。2008-09-01版权所有：杨波，武汉科技大学理学院 快速分类算法快速分类算法public static void QuickSort(int p,int q)/将全程数组a1:n中的元素ap，aq按递增的方式分类。/认为an+1已被定义，且大于或等于ap:q的所有元素；即an+1=+int j;if(pq)j=q+1;/每次执行Partition时使用一个右侧附加空间p:q等同与m:p-1 /m=p;p-1=q;j=Partition(p,j);/j是划

7、分元素的位置 QuickSort(p,j-1);/对左半段排序 QuickSort(j+1,q);/对右半段排序 2008-09-01版权所有：杨波，武汉科技大学理学院 全部分类过程全部分类过程12345678916570758085605550452604550556585807570355455060658580757045045556065858075705455055606585807570645505560658580757074550556065708075858455055606570807585945505560657075808510455055606570758085200

8、8-09-01版权所有：杨波，武汉科技大学理学院 快速分类分析快速分类分析n统计的对象：元素的比较次数，记为：C(n)n两点假设q参加分类的n个元素各不相同qPartition中的划分元素v是随机选取的（针对平均情况的分析）n随机选取划分元素：q在划分区间m,p-1随机生成某一坐标：iRandom(m,p-1)；q调换am与ai;vai;aiam;im+1;作用：将随机指定的划分元素的值调换到 am位置。算法主体不变。之后，仍从am开始执行划分操作。2008-09-01版权所有：杨波，武汉科技大学理学院 递归层次递归层次QuickSort(1,n)QuickSort(1,j1-1)QuickS

9、ort(j1+1,n)QuickSort(1,j21-1)QuickSort(j21+1,j1-1)QuickSort(j1+1,j22-1)QuickSort(j22+1,n)n个元素参加划分和分类去掉1个第一级的划分元素n-1个元素参加划分和分类去掉2个第二级的划分元素n-3个元素参加划分和分类去掉4个第三级的划分元素第一层第二层第三层 设在任一级递归调用上，调用Partition处理的所有元素总数为r，则，初始时r=n，以后的每级递归上，由于删去了上一级的划分元素，故r比上一级至少1：理想情况，（与前一级相比）第二级少1，第三级少2，第四级少4，；最坏情况，每次仅减少1（每次选取的划分元

10、素刚好是当前集合中最小或最大者）2008-09-01版权所有：杨波，武汉科技大学理学院 最坏情况分析最坏情况分析n记最坏情况下的元素比较次数是Cw(n)；n设r是在任一级递归上对Partition的所有调用的元素总数。在一级只有一次调用，执行Partition(1,n+1)，且r=n，因此，比较数至多是n+1；在二级至多作两次调用（一次实际不做任何处理），且r=n-1，因此，比较数至多是n等等。因此，在递归的任意一级上，所有的Partition共作r+1次元素比较，而每一级的r，由于删去了前一级的划分元素，故比前一级的r至少要少1。nCw(n)是r由n变到2的和，即Cw(n)=O(n2)。20

11、08-09-01版权所有：杨波，武汉科技大学理学院 最坏情况举例最坏情况举例k01234n-1nn+1ak-n123n-2n-132()1(1)2WWnCnnCnn)()(2nnCW渐近时间复杂度2008-09-01版权所有：杨波，武汉科技大学理学院 最好情况下最好情况下32()2(1)/2)12BBnCnCnnn()(log)BCnnn 渐近时间复杂度2008-09-01版权所有：杨波，武汉科技大学理学院 平均情况分析平均情况分析 平均情况是指集合中的元素以任意顺序排列，且任选元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的平均值。设调用Partition(m,p)时，

12、所选取划分元素v恰好是am:p-1中的第i小元素（1ip-m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是am:j-1和aj+1:p-1的概率是：1/(p-m),mjp。记平均情况下的元素比较次数是CA(n)；则有：其中，n n+1是Partition第一次调用时所需的元素比较次数。n CA(0)=CA(1)=0nkAAnAknCkCnnC11)()1(1)(1)2008-09-01版权所有：杨波，武汉科技大学理学院 n)1()2()1()1()0(2)1()(nCCCnnnnCAAAA用n-1换(2)中的n(1)(1)(1)2(0)(1)(2)(3)AAAAnCnn nCCC

13、n (2)-(3)1(22)1()1()(nCnnCnnnCAAA即)4()1/(2/)1()1/()(nnnCnnCAA反复使用(4)代换CA(n-1)，CA(n-2)，得到 2008-09-01版权所有：杨波，武汉科技大学理学院 13/122/)1()1/(2/2)1/(2)2/()3()1/(2/2)1/()2()1/()(nkAAAAkCnnnnnCnnnnCnnC由于 1213)1ln(/1nnknxdxk所以)log()1ln()1(2)(nnnnnCA2008-09-01版权所有：杨波，武汉科技大学理学院 n空间分析n 最坏情况下，递归的最大深度为n-1.n 需要栈空间：O(n)

14、使用一个迭代模型可以将栈空间总量减至O(logn)&最坏时间复杂度：最坏时间复杂度：O(n2)&平均时间复杂度：平均时间复杂度：O(nlogn)&辅助空间：辅助空间：O(n)或或O(logn)2008-09-01版权所有：杨波，武汉科技大学理学院 快速分类算法的迭代模型快速分类算法的迭代模型n处理策略：每次在Partition将文件A(p:q)分成两个文件A(p:j-1)和A(j+1,q)后，先对其中较小的子文件进行分类。当小的子文件分类完成后，再对较 大的子文件进行分类。n栈：需要一个栈空间保存目前暂不分类的较大子文件。并在较小子文件分类完成后，从栈中退出最新的较大子文件进行下一步分类。n栈

15、空间需求量：O(logn)n算法终止：当栈空时，整个分类过程结束。2008-09-01版权所有：杨波，武汉科技大学理学院 QuickSort的迭代模型的迭代模型 public static void QuickSort2(int p,int q)int stack,top,j;stack=new int11;top=0;while(true)while(pq)j=q+1;j=Partition(p,j);if(j-pq-j)stacktop+1=j+1;stacktop+2=q;q=j-1;/左半文件较小先处理 /将大的子文件入栈后处理 else stacktop+1=p;stacktop+2

16、=j-1;p=j+1;/右半文件较小先处理 top=top+2;if(top=0)break;q=stacktop;p=stacktop-1;top=top-2;public static void QuickSort(int p,int q)int j;if(pq)j=q+1 j=Partition(p,j);QuickSort(p,j-1);QuickSort(j+1,q);2008-09-01版权所有：杨波，武汉科技大学理学院 快速分类算法迭代模型的空间分析快速分类算法迭代模型的空间分析设算法所需的最大栈空间是S(n)，则有 101)2/)1(2)(nnnSnS2008-09-01版权所

17、有：杨波，武汉科技大学理学院 4.6 4.6 选择问题选择问题1.问题描述问题描述 在n个元素的表a1:n中确定第k小元素，1kn。2.设计思路设计思路 利用Partition过程。在第一次划分后划分元素v测定在aj的位置上，则有j-1个元素小于或等于aj，且有n-j个元素大于或等于aj。此时，n 若k=j，则aj即是第k小元素；否则，n 若kj，则a1:n中的第k小元素将出现在aj+1:n，是aj+1:n中的第k-j小元素。2008-09-01版权所有：杨波，武汉科技大学理学院 利用利用Partition实现的选择算法实现的选择算法public static void Select(int

18、n,int k)/在数组在数组a1,an中找第中找第k小元素小元素s并把它放在位置并把它放在位置k，假设，假设1kn。/将剩下的元素按如下方式排列，使将剩下的元素按如下方式排列，使ak=t，对于，对于1mk，有，有amt；对于；对于 /kmn，有，有amt。an+1=+int m,r,j;m=1;r=n+1;an+1=10000;while(true)/每当进入这一循环时，每当进入这一循环时，1mkrn+1 j=r;/将剩余元素的最大下标加将剩余元素的最大下标加1后给后给j j=Partition(m,j);/返回返回j，它使得，它使得aj是第是第j小的值小的值 if(kj)r=j;/j是新的

19、上界是新的上界 else if(k=j)return;else m=j+1;/j+1是新的下界是新的下界 2008-09-01版权所有：杨波，武汉科技大学理学院 m=1;r=n+1;an+1=10000;while(true)j=r;j=Partition(m,j);if(k0，使得：2)1()(1)(1niTinTncnnTkinikkAikAkA因此，11111()max()(1)1max()()2ki kk i nnnkn kkR ncnR niR incnR iR inn 划分元素ik,将在i的前半部分求解2008-09-01版权所有：杨波，武汉科技大学理学院 选择cR(1)，对问题规

20、模n进行归纳，证明对于所有n2，有R(n)4cn 归纳基础归纳基础 对于n=2由上式有 1(2)2max(1),(1)2.542RcRRccn归纳假设归纳假设 假定对于所有的n，2nm，R(n)4cn。归纳步骤归纳步骤 对于n=m，1111()max()()mmkm kkR mcmR iR im 由于R(n)是n的非降函数，故可以得到当m为偶数而k=m/2时，或者当m为奇数而k=(m+1)/2时，111)()(mkmkmiRiR取极大值。因此 若m为偶数，则 11/2/228()()4mmmmcR mcmR icmicmmm若m为奇数，则 11(1)/2(1)/228()()4mmmmcR m

21、cmR icmicmmm由于 TA(n)R(n)，所以TA(n)4cn，故TA(n)=O(n)2008-09-01版权所有：杨波，武汉科技大学理学院 最坏情况时间是最坏情况时间是O(n)的选择算法的选择算法基本思想：基本思想：精心挑选划分元素v方法：方法：二次取中间值目的：目的：使v比一部分元素小比另一部分元素大2008-09-01版权所有：杨波，武汉科技大学理学院 二次取中间值二次取中间值作为划分元素作为划分元素v 首先，将参加划分的n个元素分成 组，每组有r个元素(r1)。（多余的 个元素忽略不计）然后，对这 组每组的r个元素进行分类并找出其中间元素mi,1i ，共得 个中间值。之后，对这

22、 个中间值分类，并找出其中间值mm。将mm作为划分元素执行划分。n/rn/rrn n/rn/rn/rn/r2008-09-01版权所有：杨波，武汉科技大学理学院 例：设n=35，r=7。n分为n/r=5个元素组：B1，B2，B3，B4，B5，每组7个元素。n每组7个元素沿列而下已排成一个非降序列。n每列中间的元素就是mi。而且这些列也按的mi非降次序进行排列。因此，第3列的mi就是mm。mm中间值小于等于mm的元素大于等于mm的元素非降次序B1 B2 B3 B4 B5按照mi的非降次序排列2008-09-01版权所有：杨波，武汉科技大学理学院 由于r个元素的中间值是第 小元素。则，至少有 个m

23、i小于或等于mm；至少有 个mi大于或等于mm。故，至少有 个元素小于或等于（或大于或等于）mm。当r=5，则使用两次取中间值规则来选择v=mm，可得到，至少有 个元素小于或等于选择元素v。且至多有 个元素大于v。同理，至多有 0.7n+1.2个元素小于v。故，这样的v可较好地划分a中的n个元素。/2n/r1/2n/rn/r2/n/rr/2n/55.1n1.5 n/50.7n1.2/2n/rr/25051.5/551.550.3 50.7 50.7(5)0.30.70.30.71.2nkmmnnkmkkkmkmkmmnmn2008-09-01版权所有：杨波，武汉科技大学理学院 使用二次取中规则

24、的选择算法的说明使用二次取中规则的选择算法的说明性描述性描述public static int Select2(int a,int k,int n)/在集合a中找第k小元素 若nr，则采用插入法直接对a分类并返回第k小元素。把a分成大小为r的 个子集合，忽略剩余的元素。设 是上面 个子集合的中间值的集合。用Partition划分a，v作为划分元素。假设v在位置j。case k=j:return(v);kj:设S是a1:j-1中元素的集合 return(Select2(S,k,j-1)else:设R是aj+1:n中元素的集合 return(Select2(R,k-j,n-j)rn/rnmmmM/

25、21,rn/2(,/2,/)vSelectMn rn r2008-09-01版权所有：杨波，武汉科技大学理学院 算法分析算法分析记T(n)是Select2所需的最坏情况时间对特定的r分析Select2，选取r=5。(a中的元素各不相同)2008-09-01版权所有：杨波，武汉科技大学理学院 public static int Select2(int a,int k,int n)/在集合a中找第k小元素 若nr，则采用插入法直接对a分类并返回第k小元素。把a分成大小为r的 个子集合，忽略剩余的元素。设 是上面 个子集合的中间值的集合。用Partition划分a，v作为划分元素。假设v在位置j。c

26、ase k=j:return(v);kn 两个子问题的规模和大于原问题两个子问题的规模和大于原问题。改进：取r=9。经计算可得，此时将有 个元素小于或等于v，同时至少有 大于或等于v。则当n90时，|S|和|R|都至多为：2.5 n/92.5 n/91n-2.5 n/9+(2.5 n/9)=n-1.25 n/931n/36+1.2563n/722public static int Select2(int a,int k,int n)/在集合a中找第k小元素 case k=j:return(v);kj:设S是a1:j-1中元素的集合 return(Select2(S,k,j-1)else:设R是

27、aj+1:n中元素的集合 return(Select2(R,k-j,n-j)2(,/2,/)vSelectMn rn rT(n)T(n/5)+T(3n/4)+cn2008-09-01版权所有：杨波，武汉科技大学理学院 1190()(/9)(63/72)90c nnT nT nTnc nn用归纳法可证：T(n)72c1n即：T(n)=O(n)2008-09-01版权所有：杨波，武汉科技大学理学院 Select2的实现的实现算法中需要解决的两个问题 1)如何确定子集合的中间值 当r较小时，采用InsertionSort(a,i,j)直接对每组的r个元素分类，在分类好的序列中，中间元素即为当前r个元

28、素中的中间位置下标对应的元素。2)如何保存 个子集合的中间值 注：各组找到的中间元素值将调整到数组a的前部，连续保存，从而可用递归调用的方式对这些中间值进行排序并找出中间值的中间值。rn/2008-09-01版权所有：杨波，武汉科技大学理学院 算法见实现的程序算法见实现的程序public static int Sel(int m,int p,int k)/返回一个i，使得i属于m,p，且ai是am:p中第k小元素，r是一个全程变量，其取值为一个大于1的整数。int i,j,n,temp;if(p-m+1=r)InsertionSort(m,p);return(m+k-1);/返回第k小元素的位

29、置 while(true)n=p-m+1;/元素数 for(i=1;ik)p=j-1;else k=k-(j-m+1);m=j+1;2008-09-01版权所有：杨波，武汉科技大学理学院 4.7 4.7 斯特拉森矩阵乘法斯特拉森矩阵乘法 设矩阵A和B是两个nn矩阵，讨论矩阵加法的时间复杂度和矩阵乘法的时间复杂度。矩阵加法加法：(n2)矩阵乘法乘法：(n3)2008-09-01版权所有：杨波，武汉科技大学理学院 分治法解决矩阵乘法（降低计算复杂分治法解决矩阵乘法（降低计算复杂度）度）假设：n=2k111211121112212221222122AABBCCAABBCC其中：11111112211

30、21112122221211122212221122222CA BA BCA BA BCA BA BCA BA B2008-09-01版权所有：杨波，武汉科技大学理学院 复杂度分析复杂度分析2)2/(82)(2ndnnTnbnT)()(3nnT渐近复杂度2008-09-01版权所有：杨波，武汉科技大学理学院 观察：矩阵乘法的花费比矩阵加法大（O(n3)对O(n2)）。技巧：增加加法减少乘法2008-09-01版权所有：杨波，武汉科技大学理学院 令：112211222122111112222221111112222111111212222122()()()()()()()()()()PAABBQ

31、AABRABBSABBTAABUAABBVAABB则：11122122CPSTVCPTCQSCPRQU7个乘法和个乘法和10个加个加（减）法（减）法 8个加（减）法个加（减）法 2008-09-01版权所有：杨波，武汉科技大学理学院 斯特拉森时间复杂度斯特拉森时间复杂度22()7(/2)2bnT nT nann2212logloglog4 log7 log4log7log7log72.81()(1 7/4(7/4)(7/4)7(1)(7/4)7(1)()()kknnT nanTcncnncnnn 2008-09-01版权所有：杨波，武汉科技大学理学院 Strassen是如何发现的？是如何发现的

32、？n谁知道?n一种可能的方法：分析法q4个式子q8种基本元素Aij，Bijq有可能少于8次乘法完成q如何利用7次乘法计算其实，世上最温暖的语言，“不是我爱你，而是在一起。”所以懂得才是最美的相遇！只有彼此以诚相待，彼此尊重，相互包容，相互懂得，才能走的更远。相遇是缘，相守是爱。缘是多么的妙不可言，而懂得又是多么的难能可贵。否则就会错过一时，错过一世！择一人深爱，陪一人到老。一路相扶相持，一路心手相牵，一路笑对风雨。在平凡的世界，不求爱的轰轰烈烈；不求誓言多么美丽；唯愿简单的相处，真心地付出，平淡地相守，才不负最美的人生；不负善良的自己。人海茫茫，不求人人都能刻骨铭心，但求对人对己问心无愧，无怨

33、无悔足矣。大千世界，与万千人中遇见，只是相识的开始，只有彼此真心付出，以心交心，以情换情，相知相惜，才能相伴美好的一生，一路同行。然而，生活不仅是诗和远方，更要面对现实。如果曾经的拥有，不能天长地久，那么就要学会华丽地转身，学会忘记。忘记该忘记的人，忘记该忘记的事儿，忘记苦乐年华的悲喜交集。人有悲欢离合，月有阴晴圆缺。对于离开的人，不必折磨自己脆弱的生命，虚度了美好的朝夕；不必让心灵痛苦不堪，弄丢了快乐的自己。擦汗眼泪，告诉自己，日子还得继续，谁都不是谁的唯一，相信最美的风景一直在路上。人生，就是一场修行。你路过我，我忘记你；你有情，他无意。谁都希望在正确的时间遇见对的人，然而事与愿违时，你越

34、渴望的东西，也许越是无情无义地弃你而去。所以美好的愿望，就会像肥皂泡一样破灭，只能在错误的时间遇到错的人。岁月匆匆像一阵风，有多少故事留下感动。愿曾经的相遇，无论是锦上添花，还是追悔莫及；无论是青涩年华的懵懂赏识，还是成长岁月无法躲避的经历愿曾经的过往，依然如花芬芳四溢，永远无悔岁月赐予的美好相遇。其实，人生之路的每一段相遇，都是一笔财富，尤其亲情、友情和爱情。在漫长的旅途上，他们都会丰富你的生命，使你的生命更充实，更真实；丰盈你的内心，使你的内心更慈悲，更善良。所以生活的美好，缘于一颗善良的心，愿我们都能善待自己和他人。一路走来，愿相亲相爱的人，相濡以沫，同甘共苦，百年好合。愿有情有意的人，不离不弃，相惜相守，共度人生的每一个朝夕直到老得哪也去不了，依然是彼此手心里的宝，感恩一路有你！感谢您对文章的阅读跟下载，希望本篇文章能帮助到您，建议您下载后自己先查看一遍，把用不上的部分页面删掉哦，当然包括最后一页，最后祝您生活愉快!