算法分析与设计第四章3(分治法快速分类)课件_第1页
算法分析与设计第四章3(分治法快速分类)课件_第2页
算法分析与设计第四章3(分治法快速分类)课件_第3页
算法分析与设计第四章3(分治法快速分类)课件_第4页
算法分析与设计第四章3(分治法快速分类)课件_第5页
已阅读5页,还剩97页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

2008-09-01版权所有:杨波,武汉科技大学理学院第四章分治法2008-09-01版权所有:杨波,武汉科技大学理学院第四2008-09-01版权所有:杨波,武汉科技大学理学院§4.5快速分类1.划分与快速分类快速分类是一种基于划分的分类方法;

划分:选取待分类集合A中的某个元素t,按照与t的大小关系重新整理A中元素,使得整理后t被置于序列的某位置上,而序列中所有在t以前出现的元素均小于等于t,而所有出现在t以后的元素均大于等于t。这一元素的整理过程称为

划分(Partitioning)。元素t称为划分元素。

快速分类:通过反复地对待排序集合进行划分达到分类目的的分类算法。2008-09-01版权所有:杨波,武汉科技大学理学院§42008-09-01版权所有:杨波,武汉科技大学理学院快速分类的基本思想

对于输入的子数组a[m:p-1],按以下3个步骤进行排序:

分解(divide):以a[m]为基准元素(假定第一个元素a[m]是划分元素)将a[m:p-1]分成3段a[m:q-1],a[q]和a[q+1:p-1],使得a[m:q-1]中任何元素小于等于a[q],a[q+1:p-1]中任何元素大于等于a[q],下标q在划分过程中确定。递归求解(conquer):通过递归调用快速排序算法,分别对a[m:q-1]和a[q+1:p-1]进行排序。合并(merge):由于对a[m:q-1]和a[q+1:p-1]的排序是就地进行的,所以在a[m:q-1]和a[q+1:p-1]都已排好序后不需要执行任何计算,a[m:p-1]就已排好序。2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院划分过程的算法描述publicstaticintPartition(intm,intp){//在a[m],a[m+1],…,a[p-1]中的元素按如下方式重新排列:如果最初t=a[m],则在重排完成之后,

//对于m和p-1之间的某个q,有a[q]=t,并使得对于m≤k≤q,有a[k]≤t,而对于q<k<p,有a[k]≥t。

//退出时返回值为划分元素所在的下标位置

inti,v;//v为划分元素,i为从左到右计数,p从右到左计数

v=a[m];i=m+1;p=p-1;inttemp;//临时交换单元

while(true){while(a[i]<v)i++;//直到不小于v,i向右移动

while(a[p]>v)p--;//直到不大于v,p向左移动

if(i<p)//a[i]与a[p]交换位置

{temp=a[i];a[i]=a[p];a[p]=temp;}elsebreak;}a[m]=a[p];a[p]=v;//划分元素在位置preturnp;}a[p]被定义,但为一限界值a[p]≥a[m],不包含在实际的分类区间内。(技巧:假如是按照从大到小排列,经过Partition算法之后进行从小到大排列,引入a[p]则程序易于实现)算法对集合a[m:p-1]进行划分元素a[m]作为划分元素2008-09-01版权所有:杨波,武汉科技大学理学院划分2008-09-01版权所有:杨波,武汉科技大学理学院划分实例(1次划分)12345678910iP65707580856055504510000296545758085605550701000038654550808560557570100004765455055856080757010000566545505560858075701000065604550556585807570100005Partition(m,p)=Partition(1,10)划分元素p=52008-09-01版权所有:杨波,武汉科技大学理学院划分2008-09-01版权所有:杨波,武汉科技大学理学院经过一次“划分”后,实现了对集合元素的调整:以划分元素为界,左边子集合的所有元素均小于等于右边子集合的所有元素。按同样的策略对两个子集合进行分类处理。当子集合分类完毕后,整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类方法称为快速分类。2008-09-01版权所有:杨波,武汉科技大学理学院经过2008-09-01版权所有:杨波,武汉科技大学理学院快速分类算法publicstaticvoidQuickSort(intp,intq){//将全程数组a[1:n]中的元素a[p],…,a[q]按递增的方式分类。

//认为a[n+1]已被定义,且大于或等于a[p:q]的所有元素;即a[n+1]=+∞intj;if(p<q){j=q+1;//每次执行Partition时使用一个右侧附加空间[p:q]等同与[m:p-1]//m=p;p-1=q;j=Partition(p,j);//j是划分元素的位置

QuickSort(p,j-1);//对左半段排序

QuickSort(j+1,q);//对右半段排序

}}2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院全部分类过程1234567891[657075808560555045]2[60455055]65[85807570]3[554550]6065[85807570]4[5045]556065[85807570]5[45]50556065[85807570]64550556065[85807570]74550556065[708075]858455055606570[8075]859455055606570[75]8085104550556065707580852008-09-01版权所有:杨波,武汉科技大学理学院全部2008-09-01版权所有:杨波,武汉科技大学理学院快速分类分析统计的对象:元素的比较次数,记为:C(n)两点假设参加分类的n个元素各不相同Partition中的划分元素v是随机选取的(针对平均情况的分析)随机选取划分元素:在划分区间[m,p-1]随机生成某一坐标:i←Random(m,p-1);调换a[m]与a[i];v←a[i];a[i]←a[m];i←m+1;

作用:将随机指定的划分元素的值调换到a[m]位置。算法主体不变。之后,仍从a[m]开始执行划分操作。2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院递归层次QuickSort(1,n)QuickSort(1,j1-1)QuickSort(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(每次选取的划分元素刚好是当前集合中最小或最大者)2008-09-01版权所有:杨波,武汉科技大学理学院递归2008-09-01版权所有:杨波,武汉科技大学理学院最坏情况分析记最坏情况下的元素比较次数是Cw(n);设r是在任一级递归上对Partition的所有调用的元素总数。在一级只有一次调用,执行Partition(1,n+1),且r=n,因此,比较数至多是n+1;在二级至多作两次调用(一次实际不做任何处理),且r=n-1,因此,比较数至多是n等等。因此,在递归的任意一级上,所有的Partition共作r+1次元素比较,而每一级的r,由于删去了前一级的划分元素,故比前一级的r至少要少1。Cw(n)是r由n变到2的和,即Cw(n)=O(n2)。2008-09-01版权所有:杨波,武汉科技大学理学院最坏2008-09-01版权所有:杨波,武汉科技大学理学院最坏情况举例k01234…n-1nn+1a[k]--n123…n-2n-1∞渐近时间复杂度2008-09-01版权所有:杨波,武汉科技大学理学院最坏2008-09-01版权所有:杨波,武汉科技大学理学院最好情况下渐近时间复杂度2008-09-01版权所有:杨波,武汉科技大学理学院最好2008-09-01版权所有:杨波,武汉科技大学理学院平均情况分析

平均情况是指集合中的元素以任意顺序排列,且任选元素作为划分元素进行划分和分类,在这些所有可能的情况下,算法执行性能的平均值。设调用Partition(m,p)时,所选取划分元素v恰好是a[m:p-1]中的第i小元素(1≤i≤p-m)的概率相等。则经过一次划分,所留下的待分类的两个子文件恰好是a[m:j-1]和a[j+1:p-1]的概率是:1/(p-m),m≤j<p。记平均情况下的元素比较次数是CA(n);则有:

其中,

n+1是Partition第一次调用时所需的元素比较次数。

CA(0)=CA(1)=0(1)2008-09-01版权所有:杨波,武汉科技大学理学院平均2008-09-01版权所有:杨波,武汉科技大学理学院用n-1换(2)中的n

(2)-(3)

反复使用(4)代换CA(n-1),CA(n-2),…,得到

2008-09-01版权所有:杨波,武汉科技大学理学院用n2008-09-01版权所有:杨波,武汉科技大学理学院由于所以

2008-09-01版权所有:杨波,武汉科技大学理学院由于2008-09-01版权所有:杨波,武汉科技大学理学院空间分析最坏情况下,递归的最大深度为n-1.

需要栈空间:O(n)

使用一个迭代模型可以将栈空间总量减至O(logn)最坏时间复杂度:O(n2)平均时间复杂度:O(nlogn)辅助空间:O(n)或O(logn)2008-09-01版权所有:杨波,武汉科技大学理学院空间2008-09-01版权所有:杨波,武汉科技大学理学院快速分类算法的迭代模型处理策略:每次在Partition将文件A(p:q)分成两个文件A(p:j-1)和A(j+1,q)后,先对其中较小的子文件进行分类。当小的子文件分类完成后,再对较大的子文件进行分类。栈:需要一个栈空间保存目前暂不分类的较大子文件。并在较小子文件分类完成后,从栈中退出最新的较大子文件进行下一步分类。栈空间需求量:O(logn)算法终止:当栈空时,整个分类过程结束。2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院QuickSort的迭代模型publicstaticvoidQuickSort2(intp,intq){intstack[],top,j;stack=newint[11];top=0;while(true){while(p<q){j=q+1;j=Partition(p,j);if(j-p<q-j){stack[top+1]=j+1;stack[top+2]=q;q=j-1;//左半文件较小先处理

}//将大的子文件入栈后处理

else{stack[top+1]=p;stack[top+2]=j-1;p=j+1;//右半文件较小先处理

}top=top+2;}if(top==0)break;q=stack[top];p=stack[top-1];top=top-2;}}publicstaticvoidQuickSort(intp,intq){intj;if(p<q){j=q+1j=Partition(p,j);QuickSort(p,j-1);QuickSort(j+1,q);}}2008-09-01版权所有:杨波,武汉科技大学理学院Qu2008-09-01版权所有:杨波,武汉科技大学理学院快速分类算法迭代模型的空间分析设算法所需的最大栈空间是S(n),则有

2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院§4.6选择问题1.问题描述在n个元素的表a[1:n]中确定第k小元素,1≤k≤n。2.设计思路利用Partition过程。在第一次划分后划分元素v测定在a[j]的位置上,则有j-1个元素小于或等于a[j],且有n-j个元素大于或等于a[j]。此时,若k=j,则a[j]即是第k小元素;否则,若k<j,则a[1:n]中的第k小元素将出现在a[1:j-1]中,

且仍是a[1:j-1]中的第k小元素;若k>j,则a[1:n]中的第k小元素将出现在a[j+1:n],是a[j+1:n]中的第k-j小元素。2008-09-01版权所有:杨波,武汉科技大学理学院§42008-09-01版权所有:杨波,武汉科技大学理学院利用Partition实现的选择算法publicstaticvoidSelect(intn,intk){//在数组a[1],…,a[n]中找第k小元素s并把它放在位置k,假设1≤k≤n。

//将剩下的元素按如下方式排列,使a[k]=t,对于1≤m<k,有a[m]≤t;对于

//k<m≤n,有a[m]≥t。a[n+1]=+∞intm,r,j;m=1;r=n+1;a[n+1]=10000;while(true)//每当进入这一循环时,1≤m≤k≤r≤n+1{j=r;//将剩余元素的最大下标加1后给jj=Partition(m,j);//返回j,它使得a[j]是第j小的值

if(k<j)r=j;//j是新的上界

elseif(k==j)return;elsem=j+1;//j+1是新的下界

}}2008-09-01版权所有:杨波,武汉科技大学理学院利用2008-09-01版权所有:杨波,武汉科技大学理学院m=1;r=n+1;a[n+1]=10000;while(true){j=r;j=Partition(m,j);if(k<j)r=j;elseif(k==j)return;elsem=j+1;}2008-09-01版权所有:杨波,武汉科技大学理学院2008-09-01版权所有:杨波,武汉科技大学理学院算法分析两点假设①a中的元素互异②随机选取划分元素,且选择a[m:p-1]中任一元素作为划分元素的概率相同分析在Select中每次调用Partition(m,j),所需的元素比较次数是

j-m+1。在执行一次Partition后,或者找到第k小元素,或者将在缩小的子集(a[m,k-1]或a[k+1,j])中继续查找。缩小的子集的元素数将至少比上一次划分的元素数少1。2008-09-01版权所有:杨波,武汉科技大学理学院算法2008-09-01版权所有:杨波,武汉科技大学理学院最坏情况Select的最坏情况时间是O(n2)

最坏情况下的特例:输入a恰好使对Partition的第i次调用选用的划分元素是第i小元素,而k=n。此时,(区间下界)m随着Partition的每一次调用而仅增加1,j保持不变。Partition最终需要调用n次。则n次调用的时间总量是:2008-09-01版权所有:杨波,武汉科技大学理学院最坏2008-09-01版权所有:杨波,武汉科技大学理学院平均情况设是找a[1:n]的第k小元素的平均时间;TA(n)是Select的平均计算时间。则有:定义则有:对n个不同的元素,问题实例可能的n!种不同情况,综合考查所得的平均值在所有可能的情况下,找所有可能的k小元素某个特定的k2008-09-01版权所有:杨波,武汉科技大学理学院平均2008-09-01版权所有:杨波,武汉科技大学理学院定理:Select的平均计算时间TA(n)是O(n)。证明:在对Partition第一次调用时,划分元素v是第i小元素的概率为1/n,1≤i≤n(这是根据v的随机选择所确定的)。而Partition和Select中选择语句所要求的时间是O(n)。因此,存在常数c,c>0,使得:因此,

划分元素i<k,将在i的后半部分求解划分元素i>k,将在i的前半部分求解2008-09-01版权所有:杨波,武汉科技大学理学院定理2008-09-01版权所有:杨波,武汉科技大学理学院选择c≥R(1),对问题规模n进行归纳,证明对于所有n≥2,有R(n)≤4cn

归纳基础对于n=2由上式有归纳假设假定对于所有的n,2≤n<m,R(n)≤4cn。归纳步骤对于n=m,

由于R(n)是n的非降函数,故可以得到当m为偶数而k=m/2时,或者当m为奇数而k=(m+1)/2时,取极大值。因此若m为偶数,则若m为奇数,则由于TA(n)≤R(n),所以TA(n)≤4cn,故TA(n)=O(n)2008-09-01版权所有:杨波,武汉科技大学理学院选择2008-09-01版权所有:杨波,武汉科技大学理学院最坏情况时间是O(n)的选择算法基本思想:精心挑选划分元素v方法:二次取中间值目的:使v比一部分元素小比另一部分元素大2008-09-01版权所有:杨波,武汉科技大学理学院最坏2008-09-01版权所有:杨波,武汉科技大学理学院二次取中间值作为划分元素v

首先,将参加划分的n个元素分成组,每组有r个元素(r≥1)。(多余的个元素忽略不计)然后,对这组每组的r个元素进行分类并找出其中间元素mi,1≤i≤,共得个中间值。之后,对这个中间值分类,并找出其中间值mm。将mm作为划分元素执行划分。2008-09-01版权所有:杨波,武汉科技大学理学院二次2008-09-01版权所有:杨波,武汉科技大学理学院例:设n=35,r=7。分为n/r=5个元素组:B1,B2,B3,B4,B5,每组7个元素。每组7个元素沿列而下已排成一个非降序列。每列中间的元素就是mi。而且这些列也按的mi非降次序进行排列。因此,第3列的mi就是mm。mm中间值小于等于mm的元素大于等于mm的元素非降次序B1B2B3B4B5按照mi的非降次序排列2008-09-01版权所有:杨波,武汉科技大学理学院例:2008-09-01版权所有:杨波,武汉科技大学理学院

由于r个元素的中间值是第小元素。则,至少有个mi小于或等于mm;至少有个mi大于或等于mm。故,至少有个元素小于或等于(或大于或等于)mm。

当r=5,则使用两次取中间值规则来选择v=mm,可得到,至少有个元素小于或等于选择元素v。且至多有个元素大于v。同理,至多有0.7n+1.2个元素小于v。

故,这样的v可较好地划分a中的n个元素。2008-09-01版权所有:杨波,武汉科技大学理学院2008-09-01版权所有:杨波,武汉科技大学理学院使用二次取中规则的选择算法的说明性描述publicstaticintSelect2(inta[],intk,intn){//在集合a中找第k小元素①若n≤r,则采用插入法直接对a分类并返回第k小元素。②把a分成大小为r的个子集合,忽略剩余的元素。③设是上面个子集合的中间值的集合。④⑤用Partition划分a,v作为划分元素。⑥假设v在位置j。

⑦casek=j:return(v);k<j:设S是a[1:j-1]中元素的集合

return(Select2(S,k,j-1))else:设R是a[j+1:n]中元素的集合

return(Select2(R,k-j,n-j))}2008-09-01版权所有:杨波,武汉科技大学理学院使用2008-09-01版权所有:杨波,武汉科技大学理学院算法分析记T(n)是Select2所需的最坏情况时间对特定的r分析Select2,选取r=5。(a中的元素各不相同)2008-09-01版权所有:杨波,武汉科技大学理学院算法2008-09-01版权所有:杨波,武汉科技大学理学院publicstaticintSelect2(inta[],intk,intn){//在集合a中找第k小元素①若n≤r,则采用插入法直接对a分类并返回第k小元素。②把a分成大小为r的个子集合,忽略剩余的元素。③设是上面个子集合的中间值的集合。④⑤用Partition划分a,v作为划分元素。⑥假设v在位置j。

⑦casek=j:return(v);k<j:设S是a[1:j-1]中元素的集合

return(Select2(S,k,j-1))else:设R是a[j+1:n]中元素的集合

return(Select2(R,k-j,n-j))}O(1)O(n)O(1)O(n)T(n/5)O(n)T(3n/4)2008-09-01版权所有:杨波,武汉科技大学理学院pu2008-09-01版权所有:杨波,武汉科技大学理学院对于n≥24得:T(n)≤T(n/5)+T(3n/4)+cn对于n≤24,T(n)显然是一线性时间,只要将c取得足够大,这线性时间就可表示成T(n)≤cn归纳法容易证明:对于n≥1,有T(n)≤20cn2008-09-01版权所有:杨波,武汉科技大学理学院对于2008-09-01版权所有:杨波,武汉科技大学理学院当A中的元素不是完全不相同步骤⑤经Partition调用所产生的S和R两个子集合中可能存在一些元素等于划分元素v,可能导致|S|或|R|大于0.7n+1.2。改进:方法一:将A集合分成3个子集合U,S和R,其中U是由A中所有与v相同的元素组成,S是由A中所有比v小的元素组成,R则是A中所有比v大的元素组成。同时步骤⑦更改:

case|S|≥k:return(Select2(S,k,|S|)|S|+|U|≥k:return(v)else:return(Select2(R,k-|S|-|U|,|R|))

从而保证|S|和|R|≤0.7n+1.2成立,故关于T(n)的分析仍然成立。

T(n)=O(n)2008-09-01版权所有:杨波,武汉科技大学理学院当A2008-09-01版权所有:杨波,武汉科技大学理学院方法二:选取其他的r值进行计算

特例:当r=5,且a中的元素不是完全不同。假设其中有0.7n+1.2个元素比v小而其余的元素都等于v的情况。则,经过Partition,在这些等于v的元素中至多有一半可能在S中,故|S|≤0.7n+1.2+(0.3n-1.2)/2=0.85n+0.6

同理,|R|≤0.85n+0.6

可得,此时步骤④和⑦所处理的元素总数将是

1.05n+0.6>n

两个子问题的规模和大于原问题。

改进:取r=9。经计算可得,此时将有个元素小于或等于v,同时至少有大于或等于v。则当n≥90时,|S|和|R|都至多为:publicstaticintSelect2(inta[],intk,intn){//在集合a中找第k小元素①②③④⑤⑥

⑦casek=j:return(v);k<j:设S是a[1:j-1]中元素的集合

return(Select2(S,k,j-1))else:设R是a[j+1:n]中元素的集合

return(Select2(R,k-j,n-j))}T(n)≤T(n/5)+T(3n/4)+cn2008-09-01版权所有:杨波,武汉科技大学理学院方法2008-09-01版权所有:杨波,武汉科技大学理学院用归纳法可证:T(n)≤72c1n即:T(n)=O(n)2008-09-01版权所有:杨波,武汉科技大学理学院用归2008-09-01版权所有:杨波,武汉科技大学理学院Select2的实现算法中需要解决的两个问题

1)如何确定子集合的中间值当r较小时,采用InsertionSort(a,i,j)直接对每组的r个元素分类,在分类好的序列中,中间元素即为当前r个元素中的中间位置下标对应的元素。

2)如何保存个子集合的中间值注:各组找到的中间元素值将调整到数组a的前部,连续保存,从而可用递归调用的方式对这些中间值进行排序并找出中间值的中间值。2008-09-01版权所有:杨波,武汉科技大学理学院Se2008-09-01版权所有:杨波,武汉科技大学理学院算法见实现的程序publicstaticintSel(intm,intp,intk){//返回一个i,使得i属于[m,p],且a[i]是a[m:p]中第k小元素,r是一个全程变量,其取值为一个大于1的整数。

inti,j,n,temp;if(p-m+1<=r){InsertionSort(m,p);return(m+k-1);//返回第k小元素的位置

}while(true){n=p-m+1;//元素数

for(i=1;i<=n/r;i++)//计算中间值

{InsertionSort(m+(i-1)*r,m+i*r-1);//将中间值收集到a[m:p]的前部

temp=a[m+i-1];a[m+i-1]=a[m+(i-1)*r+r/2-1];a[m+(i-1)*r+r/2-1]=temp;}j=Sel(m,m+n/r-1,((n/r)+1)/2);//二次取中求mmtemp=a[m];a[m]=a[j];a[j]=temp;//交换a[m]与a[j]j=Partition(m,p);if((j-m+1)==k)return(j);elseif(j-m+1>k)p=j-1;else{k=k-(j-m+1);m=j+1;}}}2008-09-01版权所有:杨波,武汉科技大学理学院算法2008-09-01版权所有:杨波,武汉科技大学理学院§4.7斯特拉森矩阵乘法

设矩阵A和B是两个n×n矩阵,讨论矩阵加法的时间复杂度和矩阵乘法的时间复杂度。矩阵加法:Θ(n2)矩阵乘法:Θ(n3)2008-09-01版权所有:杨波,武汉科技大学理学院§42008-09-01版权所有:杨波,武汉科技大学理学院分治法解决矩阵乘法(降低计算复杂度)假设:n=2k其中:2008-09-01版权所有:杨波,武汉科技大学理学院分治2008-09-01版权所有:杨波,武汉科技大学理学院复杂度分析渐近复杂度2008-09-01版权所有:杨波,武汉科技大学理学院复杂2008-09-01版权所有:杨波,武汉科技大学理学院观察:矩阵乘法的花费比矩阵加法大(O(n3)对O(n2))。技巧:增加加法减少乘法2008-09-01版权所有:杨波,武汉科技大学理学院观察2008-09-01版权所有:杨波,武汉科技大学理学院令:则:7个乘法和10个加(减)法8个加(减)法2008-09-01版权所有:杨波,武汉科技大学理学院令:2008-09-01版权所有:杨波,武汉科技大学理学院斯特拉森时间复杂度2008-09-01版权所有:杨波,武汉科技大学理学院斯特2008-09-01版权所有:杨波,武汉科技大学理学院Strassen是如何发现的?谁知道?一种可能的方法:分析法4个式子8种基本元素Aij,Bij有可能少于8次乘法完成如何利用7次乘法计算2008-09-01版权所有:杨波,武汉科技大学理学院St算法分析与设计第四章3(分治法快速分类)课件算法分析与设计第四章3(分治法快速分类)课件

其实,世上最温暖的语言,“不是我爱你,而是在一起。”

所以懂得才是最美的相遇!只有彼此以诚相待,彼此尊重,相互包容,相互懂得,才能走的更远。相遇是缘,相守是爱。缘是多么的妙不可言,而懂得又是多么的难能可贵。否则就会错过一时,错过一世!择一人深爱,陪一人到老。一路相扶相持,一路心手相牵,一路笑对风雨。在平凡的世界,不求爱的轰轰烈烈;不求誓言多么美丽;唯愿简单的相处,真心地付出,平淡地相守,才不负最美的人生;不负善良的自己。人海茫茫,不求人人都能刻骨铭心,但求对人对己问心无愧,无怨无悔足矣。大千世界,与万千人中遇见,只是相识的开始,只有彼此真心付出,以心交心,以情换情,相知相惜,才能相伴美好的一生,一路同行。然而,生活不仅是诗和远方,更要面对现实。如果曾经的拥有,不能天长地久,那么就要学会华丽地转身,学会忘记。忘记该忘记的人,忘记该忘记的事儿,忘记苦乐年华的悲喜交集。人有悲欢离合,月有阴晴圆缺。对于离开的人,不必折磨自己脆弱的生命,虚度了美好的朝夕;不必让心灵痛苦不堪,弄丢了快乐的自己。擦汗眼泪,告诉自己,日子还得继续,谁都不是谁的唯一,相信最美的风景一直在路上。人生,就是一场修行。你路过我,我忘记你;你有情,他无意。谁都希望在正确的时间遇见对的人,然而事与愿违时,你越渴望的东西,也许越是无情无义地弃你而去。所以美好的愿望,就会像肥皂泡一样破灭,只能在错误的时间遇到错的人。岁月匆匆像一阵风,有多少故事留下感动。愿曾经的相遇,无论是锦上添花,还是追悔莫及;无论是青涩年华的懵懂赏识,还是成长岁月无法躲避的经历……愿曾经的过往,依然如花芬芳四溢,永远无悔岁月赐予的美好相遇。其实,人生之路的每一段相遇,都是一笔财富,尤其亲情、友情和爱情。在漫长的旅途上,他们都会丰富你的生命,使你的生命更充实,更真实;丰盈你的内心,使你的内心更慈悲,更善良。所以生活的美好,缘于一颗善良的心,愿我们都能善待自己和他人。一路走来,愿相亲相爱的人,相濡以沫,同甘共苦,百年好合。愿有情有意的人,不离不弃,相惜相守,共度人生的每一个朝夕……直到老得哪也去不了,依然是彼此手心里的宝,感恩一路有你!感谢您对文章的阅读跟下载,希望本篇文章能帮助到您,建议您下载后自己先查看一遍,把用不上的部分页面删掉哦,当然包括最后一页,最后祝您生活愉快!其实,世上最温暖的语言,“不是我爱你,而是在一起。”

2008-09-01版权所有:杨波,武汉科技大学理学院第四章分治法2008-09-01版权所有:杨波,武汉科技大学理学院第四2008-09-01版权所有:杨波,武汉科技大学理学院§4.5快速分类1.划分与快速分类快速分类是一种基于划分的分类方法;

划分:选取待分类集合A中的某个元素t,按照与t的大小关系重新整理A中元素,使得整理后t被置于序列的某位置上,而序列中所有在t以前出现的元素均小于等于t,而所有出现在t以后的元素均大于等于t。这一元素的整理过程称为

划分(Partitioning)。元素t称为划分元素。

快速分类:通过反复地对待排序集合进行划分达到分类目的的分类算法。2008-09-01版权所有:杨波,武汉科技大学理学院§42008-09-01版权所有:杨波,武汉科技大学理学院快速分类的基本思想

对于输入的子数组a[m:p-1],按以下3个步骤进行排序:

分解(divide):以a[m]为基准元素(假定第一个元素a[m]是划分元素)将a[m:p-1]分成3段a[m:q-1],a[q]和a[q+1:p-1],使得a[m:q-1]中任何元素小于等于a[q],a[q+1:p-1]中任何元素大于等于a[q],下标q在划分过程中确定。递归求解(conquer):通过递归调用快速排序算法,分别对a[m:q-1]和a[q+1:p-1]进行排序。合并(merge):由于对a[m:q-1]和a[q+1:p-1]的排序是就地进行的,所以在a[m:q-1]和a[q+1:p-1]都已排好序后不需要执行任何计算,a[m:p-1]就已排好序。2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院划分过程的算法描述publicstaticintPartition(intm,intp){//在a[m],a[m+1],…,a[p-1]中的元素按如下方式重新排列:如果最初t=a[m],则在重排完成之后,

//对于m和p-1之间的某个q,有a[q]=t,并使得对于m≤k≤q,有a[k]≤t,而对于q<k<p,有a[k]≥t。

//退出时返回值为划分元素所在的下标位置

inti,v;//v为划分元素,i为从左到右计数,p从右到左计数

v=a[m];i=m+1;p=p-1;inttemp;//临时交换单元

while(true){while(a[i]<v)i++;//直到不小于v,i向右移动

while(a[p]>v)p--;//直到不大于v,p向左移动

if(i<p)//a[i]与a[p]交换位置

{temp=a[i];a[i]=a[p];a[p]=temp;}elsebreak;}a[m]=a[p];a[p]=v;//划分元素在位置preturnp;}a[p]被定义,但为一限界值a[p]≥a[m],不包含在实际的分类区间内。(技巧:假如是按照从大到小排列,经过Partition算法之后进行从小到大排列,引入a[p]则程序易于实现)算法对集合a[m:p-1]进行划分元素a[m]作为划分元素2008-09-01版权所有:杨波,武汉科技大学理学院划分2008-09-01版权所有:杨波,武汉科技大学理学院划分实例(1次划分)12345678910iP65707580856055504510000296545758085605550701000038654550808560557570100004765455055856080757010000566545505560858075701000065604550556585807570100005Partition(m,p)=Partition(1,10)划分元素p=52008-09-01版权所有:杨波,武汉科技大学理学院划分2008-09-01版权所有:杨波,武汉科技大学理学院经过一次“划分”后,实现了对集合元素的调整:以划分元素为界,左边子集合的所有元素均小于等于右边子集合的所有元素。按同样的策略对两个子集合进行分类处理。当子集合分类完毕后,整个集合的分类也完成了。这一过程避免了子集合的归并操作。这一分类方法称为快速分类。2008-09-01版权所有:杨波,武汉科技大学理学院经过2008-09-01版权所有:杨波,武汉科技大学理学院快速分类算法publicstaticvoidQuickSort(intp,intq){//将全程数组a[1:n]中的元素a[p],…,a[q]按递增的方式分类。

//认为a[n+1]已被定义,且大于或等于a[p:q]的所有元素;即a[n+1]=+∞intj;if(p<q){j=q+1;//每次执行Partition时使用一个右侧附加空间[p:q]等同与[m:p-1]//m=p;p-1=q;j=Partition(p,j);//j是划分元素的位置

QuickSort(p,j-1);//对左半段排序

QuickSort(j+1,q);//对右半段排序

}}2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院全部分类过程1234567891[657075808560555045]2[60455055]65[85807570]3[554550]6065[85807570]4[5045]556065[85807570]5[45]50556065[85807570]64550556065[85807570]74550556065[708075]858455055606570[8075]859455055606570[75]8085104550556065707580852008-09-01版权所有:杨波,武汉科技大学理学院全部2008-09-01版权所有:杨波,武汉科技大学理学院快速分类分析统计的对象:元素的比较次数,记为:C(n)两点假设参加分类的n个元素各不相同Partition中的划分元素v是随机选取的(针对平均情况的分析)随机选取划分元素:在划分区间[m,p-1]随机生成某一坐标:i←Random(m,p-1);调换a[m]与a[i];v←a[i];a[i]←a[m];i←m+1;

作用:将随机指定的划分元素的值调换到a[m]位置。算法主体不变。之后,仍从a[m]开始执行划分操作。2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院递归层次QuickSort(1,n)QuickSort(1,j1-1)QuickSort(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(每次选取的划分元素刚好是当前集合中最小或最大者)2008-09-01版权所有:杨波,武汉科技大学理学院递归2008-09-01版权所有:杨波,武汉科技大学理学院最坏情况分析记最坏情况下的元素比较次数是Cw(n);设r是在任一级递归上对Partition的所有调用的元素总数。在一级只有一次调用,执行Partition(1,n+1),且r=n,因此,比较数至多是n+1;在二级至多作两次调用(一次实际不做任何处理),且r=n-1,因此,比较数至多是n等等。因此,在递归的任意一级上,所有的Partition共作r+1次元素比较,而每一级的r,由于删去了前一级的划分元素,故比前一级的r至少要少1。Cw(n)是r由n变到2的和,即Cw(n)=O(n2)。2008-09-01版权所有:杨波,武汉科技大学理学院最坏2008-09-01版权所有:杨波,武汉科技大学理学院最坏情况举例k01234…n-1nn+1a[k]--n123…n-2n-1∞渐近时间复杂度2008-09-01版权所有:杨波,武汉科技大学理学院最坏2008-09-01版权所有:杨波,武汉科技大学理学院最好情况下渐近时间复杂度2008-09-01版权所有:杨波,武汉科技大学理学院最好2008-09-01版权所有:杨波,武汉科技大学理学院平均情况分析

平均情况是指集合中的元素以任意顺序排列,且任选元素作为划分元素进行划分和分类,在这些所有可能的情况下,算法执行性能的平均值。设调用Partition(m,p)时,所选取划分元素v恰好是a[m:p-1]中的第i小元素(1≤i≤p-m)的概率相等。则经过一次划分,所留下的待分类的两个子文件恰好是a[m:j-1]和a[j+1:p-1]的概率是:1/(p-m),m≤j<p。记平均情况下的元素比较次数是CA(n);则有:

其中,

n+1是Partition第一次调用时所需的元素比较次数。

CA(0)=CA(1)=0(1)2008-09-01版权所有:杨波,武汉科技大学理学院平均2008-09-01版权所有:杨波,武汉科技大学理学院用n-1换(2)中的n

(2)-(3)

反复使用(4)代换CA(n-1),CA(n-2),…,得到

2008-09-01版权所有:杨波,武汉科技大学理学院用n2008-09-01版权所有:杨波,武汉科技大学理学院由于所以

2008-09-01版权所有:杨波,武汉科技大学理学院由于2008-09-01版权所有:杨波,武汉科技大学理学院空间分析最坏情况下,递归的最大深度为n-1.

需要栈空间:O(n)

使用一个迭代模型可以将栈空间总量减至O(logn)最坏时间复杂度:O(n2)平均时间复杂度:O(nlogn)辅助空间:O(n)或O(logn)2008-09-01版权所有:杨波,武汉科技大学理学院空间2008-09-01版权所有:杨波,武汉科技大学理学院快速分类算法的迭代模型处理策略:每次在Partition将文件A(p:q)分成两个文件A(p:j-1)和A(j+1,q)后,先对其中较小的子文件进行分类。当小的子文件分类完成后,再对较大的子文件进行分类。栈:需要一个栈空间保存目前暂不分类的较大子文件。并在较小子文件分类完成后,从栈中退出最新的较大子文件进行下一步分类。栈空间需求量:O(logn)算法终止:当栈空时,整个分类过程结束。2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院QuickSort的迭代模型publicstaticvoidQuickSort2(intp,intq){intstack[],top,j;stack=newint[11];top=0;while(true){while(p<q){j=q+1;j=Partition(p,j);if(j-p<q-j){stack[top+1]=j+1;stack[top+2]=q;q=j-1;//左半文件较小先处理

}//将大的子文件入栈后处理

else{stack[top+1]=p;stack[top+2]=j-1;p=j+1;//右半文件较小先处理

}top=top+2;}if(top==0)break;q=stack[top];p=stack[top-1];top=top-2;}}publicstaticvoidQuickSort(intp,intq){intj;if(p<q){j=q+1j=Partition(p,j);QuickSort(p,j-1);QuickSort(j+1,q);}}2008-09-01版权所有:杨波,武汉科技大学理学院Qu2008-09-01版权所有:杨波,武汉科技大学理学院快速分类算法迭代模型的空间分析设算法所需的最大栈空间是S(n),则有

2008-09-01版权所有:杨波,武汉科技大学理学院快速2008-09-01版权所有:杨波,武汉科技大学理学院§4.6选择问题1.问题描述在n个元素的表a[1:n]中确定第k小元素,1≤k≤n。2.设计思路利用Partition过程。在第一次划分后划分元素v测定在a[j]的位置上,则有j-1个元素小于或等于a[j],且有n-j个元素大于或等于a[j]。此时,若k=j,则a[j]即是第k小元素;否则,若k<j,则a[1:n]中的第k小元素将出现在a[1:j-1]中,

且仍是a[1:j-1]中的第k小元素;若k>j,则a[1:n]中的第k小元素将出现在a[j+1:n],是a[j+1:n]中的第k-j小元素。2008-09-01版权所有:杨波,武汉科技大学理学院§42008-09-01版权所有:杨波,武汉科技大学理学院利用Partition实现的选择算法publicstaticvoidSelect(intn,intk){//在数组a[1],…,a[n]中找第k小元素s并把它放在位置k,假设1≤k≤n。

//将剩下的元素按如下方式排列,使a[k]=t,对于1≤m<k,有a[m]≤t;对于

//k<m≤n,有a[m]≥t。a[n+1]=+∞intm,r,j;m=1;r=n+1;a[n+1]=10000;while(true)//每当进入这一循环时,1≤m≤k≤r≤n+1{j=r;//将剩余元素的最大下标加1后给jj=Partition(m,j);//返回j,它使得a[j]是第j小的值

if(k<j)r=j;//j是新的上界

elseif(k==j)return;elsem=j+1;//j+1是新的下界

}}2008-09-01版权所有:杨波,武汉科技大学理学院利用2008-09-01版权所有:杨波,武汉科技大学理学院m=1;r=n+1;a[n+1]=10000;while(true){j=r;j=Partition(m,j);if(k<j)r=j;elseif(k==j)return;elsem=j+1;}2008-09-01版权所有:杨波,武汉科技大学理学院2008-09-01版权所有:杨波,武汉科技大学理学院算法分析两点假设①a中的元素互异②随机选取划分元素,且选择a[m:p-1]中任一元素作为划分元素的概率相同分析在Select中每次调用Partition(m,j),所需的元素比较次数是

j-m+1。在执行一次Partition后,或者找到第k小元素,或者将在缩小的子集(a[m,k-1]或a[k+1,j])中继续查找。缩小的子集的元素数将至少比上一次划分的元素数少1。2008-09-01版权所有:杨波,武汉科技大学理学院算法2008-09-01版权所有:杨波,武汉科技大学理学院最坏情况Select的最坏情况时间是O(n2)

最坏情况下的特例:输入a恰好使对Partition的第i次调用选用的划分元素是第i小元素,而k=n。此时,(区间下界)m随着Partition的每一次调用而仅增加1,j保持不变。Partition最终需要调用n次。则n次调用的时间总量是:2008-09-01版权所有:杨波,武汉科技大学理学院最坏2008-09-01版权所有:杨波,武汉科技大学理学院平均情况设是找a[1:n]的第k小元素的平均时间;TA(n)是Select的平均计算时间。则有:定义则有:对n个不同的元素,问题实例可能的n!种不同情况,综合考查所得的平均值在所有可能的情况下,找所有可能的k小元素某个特定的k2008-09-01版权所有:杨波,武汉科技大学理学院平均2008-09-01版权所有:杨波,武汉科技大学理学院定理:Select的平均计算时间TA(n)是O(n)。证明:在对Partition第一次调用时,划分元素v是第i小元素的概率为1/n,1≤i≤n(这是根据v的随机选择所确定的)。而Partition和Select中选择语句所要求的时间是O(n)。因此,存在常数c,c>0,使得:因此,

划分元素i<k,将在i的后半部分求解划分元素i>k,将在i的前半部分求解2008-09-01版权所有:杨波,武汉科技大学理学院定理2008-09-01版权所有:杨波,武汉科技大学理学院选择c≥R(1),对问题规模n进行归纳,证明对于所有n≥2,有R(n)≤4cn

归纳基础对于n=2由上式有归纳假设假定对于所有的n,2≤n<m,R(n)≤4cn。归纳步骤对于n=m,

由于R(n)是n的非降函数,故可以得到当m为偶数而k=m/2时,或者当m为奇数而k=(m+1)/2时,取极大值。因此若m为偶数,则若m为奇数,则由于TA(n)≤R(n),所以TA(n)≤4cn,故TA(n)=O(n)2008-09-01版权所有:杨波,武汉科技大学理学院选择2008-09-01版权所有:杨波,武汉科技大学理学院最坏情况时间是O(n)的选择算法基本思想:精心挑选划分元素v方法:二次取中间值目的:使v比一部分元素小比另一部分元素大2008-09-01版权所有:杨波,武汉科技大学理学院最坏2008-09-01版权所有:杨波,武汉科技大学理学院二次取中间值作为划分元素v

首先,将参加划分的n个元素分成组,每组有r个元素(r≥1)。(多余的个元素忽略不计)然后,对这组每组的r个元素进行分类并找出其中间元素mi,1≤i≤,共得个中间值。之后,对这个中间值分类,并找出其中间值mm。将mm作为划分元素执行划分。2008-09-01版权所有:杨波,武汉科技大学理学院二次2008-09-01版权所有:杨波,武汉科技大学理学院例:设n=35,r=7。分为n/r=5个元素组:B1,B2,B3,B4,B5,每组7个元素。每组7个元素沿列而下已排成一个非降序列。每列中间的元素就是mi。而且这些列也按的mi非降次序进行排列。因此,第3列的mi就是mm。mm中间值小于等于mm的元素大于等于mm的元素非降次序B1B2B3B4B5按照mi的非降次序排列2008-09-01版权所有:杨波,武汉科技大学理学院例:2008-09-01版权所有:杨波,武汉科技大学理学院

由于r个元素的中间值是第小元素。则,至少有个mi小于或等于mm;至少有个mi大于或等于mm。故,至少有个元素小于或等于(或大于或等于)mm。

当r=5,则使用两次取中间值规则来选择v=mm,可得到,

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

评论

0/150

提交评论