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

《算法分析与设计第四章3(分治法快速分类).ppt》由会员分享，可在线阅读，更多相关《算法分析与设计第四章3(分治法快速分类).ppt（48页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第四章第四章 分治法分治法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都已排好序后不需要执行任何计算，am:p-1就已排好序。2008-09-01版权所

3、有：杨波，武汉科技大学理学院 划分过程的算法描述划分过程的算法描述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(aiv)p-;/直到不大于v,p向左移动 if(ip)/

4、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 10000 2965 45 75 80 85 60 55 50

5、 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是划分元素的位置 QuickSort(p,j-1);/对左半

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

8、类分析快速分类分析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)QuickSort(j1+1,n)QuickSort(1,j21-1

9、)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（每次选取的划分元素刚好是当前集合中最小或最大者）2008-09-01版权

10、所有：杨波，武汉科技大学理学院 最坏情况分析最坏情况分析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)。2008-09-01版权所有：杨波，武汉科技大学理学院 最坏

11、情况举例最坏情况举例k01234n-1nn+1ak-n123n-2n-1渐近时间复杂度2008-09-01版权所有：杨波，武汉科技大学理学院 最好情况下最好情况下渐近时间复杂度2008-09-01版权所有：杨波，武汉科技大学理学院 平均情况分析平均情况分析 平均情况是指集合中的元素以任意顺序排列，且任选元素作为划分元素进行划分和分类，在这些所有可能的情况下，算法执行性能的平均值。设调用Partition(m,p)时，所选取划分元素v恰好是am:p-1中的第i小元素（1ip-m）的概率相等。则经过一次划分，所留下的待分类的两个子文件恰好是am:j-1和aj+1:p-1的概率是：1/(p-m),m

12、jp。记平均情况下的元素比较次数是CA(n)；则有：其中，n n+1是Partition第一次调用时所需的元素比较次数。n CA(0)=CA(1)=0(1)2008-09-01版权所有：杨波，武汉科技大学理学院 用n-1换(2)中的n(2)-(3)即 反复使用(4)代换CA(n-1)，CA(n-2)，得到 2008-09-01版权所有：杨波，武汉科技大学理学院 由于 所以 2008-09-01版权所有：杨波，武汉科技大学理学院 n空间分析n 最坏情况下，递归的最大深度为n-1.n 需要栈空间：O(n)使用一个迭代模型可以将栈空间总量减至O(logn)&最坏时间复杂度：最坏时间复杂度：O(n2)

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

14、：杨波，武汉科技大学理学院 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=j-1;p=j+1;/右半文件较小先处理 top=top+2;if(top=0)break;

15、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)，则有 2008-09-01版权所有：杨波，武汉科技大学理学院 4.6 4.6 选择问题选择问题1.问题描述问题描述 在n个元素的表a1:n中确定第k小元素，1kn

16、。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 n,int k)/在数组在数组a1,an中找第中找第k小元素小元素s并把它放在位置并把它放在位置k，假设，假设1kn。/将剩下的元

17、素按如下方式排列，使将剩下的元素按如下方式排列，使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是新的上界是新的上界 else if(k=j)return;else m=j+1;/j+1是新的下界是新的下界 2008-09-01版权

18、所有：杨波，武汉科技大学理学院 m=1;r=n+1;an+1=10000;while(true)j=r;j=Partition(m,j);if(k0，使得：因此，划分元素ik,将在i的前半部分求解2008-09-01版权所有：杨波，武汉科技大学理学院 选择cR(1)，对问题规模n进行归纳，证明对于所有n2，有R(n)4cn 归纳基础归纳基础 对于n=2由上式有 归纳假设归纳假设 假定对于所有的n，2nm，R(n)4cn。归纳步骤归纳步骤 对于n=m，由于R(n)是n的非降函数，故可以得到当m为偶数而k=m/2时，或者当m为奇数而k=(m+1)/2时，取极大值。因此 若m为偶数，则 若m为奇数，

19、则 由于 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 ，共得 个中间值。之后，对这 个中间值分类，并找

20、出其中间值mm。将mm作为划分元素执行划分。2008-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个元素的中间值是第 小元素。则，至少有 个mi小于或等于mm；至少有 个mi大于或等于mm。故，至少有 个

21、元素小于或等于（或大于或等于）mm。当r=5，则使用两次取中间值规则来选择v=mm，可得到，至少有 个元素小于或等于选择元素v。且至多有 个元素大于v。同理，至多有 0.7n+1.2个元素小于v。故，这样的v可较好地划分a中的n个元素。2008-09-01版权所有：杨波，武汉科技大学理学院 使用二次取中规则的选择算法的说明使用二次取中规则的选择算法的说明性描述性描述public static int Select2(int a,int k,int n)/在集合a中找第k小元素 若nr，则采用插入法直接对a分类并返回第k小元素。把a分成大小为r的 个子集合，忽略剩余的元素。设 是上面 个子集合的

22、中间值的集合。用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)2008-09-01版权所有：杨波，武汉科技大学理学院 算法分析算法分析记T(n)是Select2所需的最坏情况时间对特定的r分析Select2，选取r=5。(a中的元素各不相同)2008-09-01版权所有：杨波，武汉科技大学理学院 public static int Select2(int a,int k,

23、int n)/在集合a中找第k小元素 若nr，则采用插入法直接对a分类并返回第k小元素。把a分成大小为r的 个子集合，忽略剩余的元素。设 是上面 个子集合的中间值的集合。用Partition划分a，v作为划分元素。假设v在位置j。case k=j:return(v);kn 两个子问题的规模和大于原问题两个子问题的规模和大于原问题。改进：取r=9。经计算可得，此时将有 个元素小于或等于v，同时至少有 大于或等于v。则当n90时，|S|和|R|都至多为：public static int Select2(int a,int k,int n)/在集合a中找第k小元素 case k=j:return(

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

25、间位置下标对应的元素。2)如何保存 个子集合的中间值 注：各组找到的中间元素值将调整到数组a的前部，连续保存，从而可用递归调用的方式对这些中间值进行排序并找出中间值的中间值。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小元素的位置 while

26、(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=2k其中：2008-09-01版权所有：杨波，武汉科技大学理学院 复杂度分析复杂度分析渐近复杂度2008-09-01版

27、权所有：杨波，武汉科技大学理学院 观察：矩阵乘法的花费比矩阵加法大（O(n3)对O(n2)）。技巧：增加加法减少乘法2008-09-01版权所有：杨波，武汉科技大学理学院 令：则：7个乘法和个乘法和10个加个加（减）法（减）法 8个加（减）法个加（减）法 2008-09-01版权所有：杨波，武汉科技大学理学院 斯特拉森时间复杂度斯特拉森时间复杂度2008-09-01版权所有：杨波，武汉科技大学理学院 Strassen是如何发现的？是如何发现的？n谁知道?n一种可能的方法：分析法q4个式子q8种基本元素Aij，Bijq有可能少于8次乘法完成q如何利用7次乘法计算2008-09-01版权所有：杨波，武汉科技大学理学院