算法设计与分析9顺序统计学ppt

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,算法设计与分析,2007.9,1,第六章 顺序统计学,顺序统计的概念,线性期望时间选择算法（过程及分析）,最坏情况线性时间选择算法（过程及分析）,程序演示及说明,2,6.1,顺序统计的概念,一、顺序统计,1,、顺序统计的概念：一个由,n,个元素组成的集合的第,i,个顺序统计就是该集合中第,i,小的元素。例如，一个集合元素中的最小值即其第一个顺序统计（,i=1,）；最大值即为其第,n,个顺序统计（,i=n,）。,2,、中位数的概念：一个中位数非正式的说即该集合的,“,中间点,”,上的元素。,3,6.2,线性期望时间选择算法,一、选择问题的定义,1,、输入：一个含,n,个（不同的）数的集合,A,和一个数,i,，,1,i,n,。,2,、输出：恰大于,A,中其他,i-1,个元素的,xA,。,二、最大最小元素的选择算法,1,、求,n,个元素集合中的最小元素,MINIMUM,（,A,）,1min A1,2for i 2 to length A,3 do if minAi,4 then minAi,5return min,通过程序可以知道经过,n-1,比较就可以确定最小值。,4,6.2,线性期望时间选择算法,三、以线形期望时间做选择,1,、,RANDOMIZED-SELECT,算法,RANDOMIZED-SELECT,（,A,p,r,i,）,1 if p=r,2 then return Ap,3 q RANDOMIZED-PARTITION(A,p,r),4 k q-p+1,5 if i,k,6 then return RANDOMIZED-SELECT(A,p,q,i),7 else return RANDOMIZED-SELECT(A,q+1,r,i-k),5,6.2,线性期望时间选择算法,2,、,RANDOMIZED-SELECT,算法运行时间分析,a.,最坏情况,RANDOMIZED-SELECT,的最坏情况运行时间为,（,n,2,）,即使是要选择最小元素也是这样，因为在每次划分时可 能极不走运，总是按所余下的元素中最大的进行划分。,b.,平均情况分析,因为是一个随机化过程,所以没有一个特别的输入会导致最坏性态的发生，所以分析该算法的平均情况性能很有实际意义，通过分析我们会发现该算法的平均情况性能较好。,6,6.2,线性期望时间选择算法,当,RANDOMIZED-SELECT,作用于一个含,n,个元素的输入数组上时，我们可以给出其期望时间的一个上界,T(n),。在快速排序算法中我们曾经分析过算法,RANDOMIZED-PARTITION,在产生划分时，其低区中含,1,个元素的概率为,2/n,，含,i,个元素的概率是,1/n,，,i=2,3,，,n-1,。假设,T(n),是单调递增的，在最坏情况下,RANDOMIZED-SELECT,的每次划分中，第,i,个元素都在划分的较大的一边。这样就得递归式：,T,（,n,）,7,6.2,线性期望时间选择算法,上面推导中由第一行到第二行是因为,max(1,n-1)=n-1,，且,如果,n,是奇数，每一项,T,（,n/2,),，,T,（,n/2,+1),，,T,（,n/2,+2),，,，,T,（,n-1),在和式中个出现了两次,;,如果,n,是偶数，每一项,T,（,n/2,+1),，,T,（,n/2,+2),，,，,T,（,n-1),个出现两次，,T,（,n/2,),只出现了一次。在各种情况中，第一行中的和式都由第二中的和式从上方限界。第二行到第三行是因为在最坏情况下,T,（,n-1,）,=O(n,2,),，故,1/nT(n-1),可被项,O(n),吸收。,8,6.2,线性期望时间选择算法,我们用归纳法解上面的递归式。假设对满足递归式初始条件的某个常数,c,，有,T(n),cn,。将其代入我们刚才,推导出来的式子,：由这个归纳假设可得：,9,6.2,线性期望时间选择算法,因为我们可以选择足够大的,c,使得,c(n/4+1/2),能支配,O(n),项。,总之，任意的顺序统计（尤其是中位数）平均来说都可在线性时间内确定。,10,6.3,最坏情况线性时间选择算法,一、,SELECT,算法的基本步骤,1,、将输入数组的,n,个元素划分成,n/5,组，每组,5,个元素，且至多只有一个组包含余下的,n mod 5,个有元素,(,如图,）。,2,、通过插入排序来找出每组中的中位数，并取其中间元素。（如果某组中有偶数个元素，则取两个中位数中较大者。）,3,、对第二步中找出的,n/5,个中位数，递归调用,SELECT,以找出其中位数,x,。,4,、用修改的,PARTITION,版本、按,x,来对输入数组进行划分。设,k,为划分的低区中的元素数，则,(n-k),为高区中的元素数。,5,、若,ik,，则在低区递归调用,SELECT,以找出第,i,小的元素；否则，若,ik,，则在高区找第（,i-k),个最小元素。,11,6.3,最坏情况线性时间选择算法,二、,SELECT,算法图解,n,个元素由小圆表示,每组占一个栏。各组的中数为白色，中数之中数,x,在图中标出。图中所画箭头是由较大元素指向较小的元素，从中可以看出每组五个元素中在,x,右边的三个大于,x,，在,x,左边的三个小于,x,。所有大于,x,的元素以阴影背景衬出。,12,6.3,最坏情况线性时间选择算法,三、,SELECT,算法的运行时间分析,第,2,步找出的中位数中，至少有一半大于,x,，除了那个所含元素可能少,5,的组和包含,x,的那个组之外。扣除这两组，所有大于,x,的元素数至少为：,3,（,1/2,n/5,-2,）,3n/10-6,同理，小于,x,的元素至少有,3n/10-6,个。故在最坏情况下，第,5,步中至多有,7n/10+6,个元素递归调用,SELECT,。,现在就可以建立一个关于算法,SELECT,的最坏情况运行时间,T(n),的递归式。第,1,，,2,，和,4,步要花,O(n),时间。（第,2,步对大小为,O(1),的集合要调用,O(n),次插入排序。）第,3,步需要时间,T (,n/5,),第,5,步需时间至多为,T,（,7n/10+6,），若假设,T,是单调递增的。请注意对,n20,，有,7n/10+680,，,c(n/10-7),大于由,O(n),项描述的函数。这就说明,SELECT,的最坏情况运行时间是线性的。,14,6.4,程序演示及说明,程序演示,15,作业,最坏情况线性时间的选择算法实现,16,The End,Thank you!,17,