《算法设计与分析9顺序统计学.ppt》由会员分享，可在线阅读，更多相关《算法设计与分析9顺序统计学.ppt（17页珍藏版）》请在三一办公上搜索。
1、算法设计与分析,谭守标安徽大学 电子学院2007.9,第六章 顺序统计学,顺序统计的概念线性期望时间选择算法（过程及分析）最坏情况线性时间选择算法（过程及分析）程序演示及说明,6.1 顺序统计的概念,一、顺序统计1、顺序统计的概念：一个由n个元素组成的集合的第i个顺序统计就是该集合中第i小的元素。例如，一个集合元素中的最小值即其第一个顺序统计（i=1）；最大值即为其第n个顺序统计（i=n）。2、中位数的概念：一个中位数非正式的说即该集合的“中间点”上的元素。,6.2 线性期望时间选择算法,一、选择问题的定义 1、输入：一个含n个（不同的）数的集合A和一个数 i，1 in。2、输出：恰大于A中其
2、他i-1个元素的xA。二、最大最小元素的选择算法 1、求n个元素集合中的最小元素 MINIMUM（A）1min A12for i 2 to length A3 do if minAi4 then minAi5return min 通过程序可以知道经过n-1比较就可以确定最小值。,6.2 线性期望时间选择算法,三、以线形期望时间做选择 1、RANDOMIZED-SELECT算法RANDOMIZED-SELECT（A,p,r,i）1 if p=r2 then return Ap3 q RANDOMIZED-PARTITION(A,p,r)4 k q-p+15 if i k6 then return
3、 RANDOMIZED-SELECT(A,p,q,i)7 else return RANDOMIZED-SELECT(A,q+1,r,i-k),6.2 线性期望时间选择算法,2、RANDOMIZED-SELECT算法运行时间分析a.最坏情况 RANDOMIZED-SELECT的最坏情况运行时间为（n2）,即使是要选择最小元素也是这样，因为在每次划分时可 能极不走运，总是按所余下的元素中最大的进行划分。b.平均情况分析因为是一个随机化过程,所以没有一个特别的输入会导致最坏性态的发生，所以分析该算法的平均情况性能很有实际意义，通过分析我们会发现该算法的平均情况性能较好。,6.2 线性期望时间选择算
4、法,当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）,6.2 线性期望时间选择算法,上面推导中由第一行到第二行是因为max(1,n-1)=n-1，且 如果n是奇数，每一项T（n/2)，T（n/2+1)，T（n/2+2)，T
5、（n-1)在和式中个出现了两次;如果n是偶数，每一项 T（n/2+1)，T（n/2+2)，T（n-1)个出现两次，T（n/2)只出现了一次。在各种情况中，第一行中的和式都由第二中的和式从上方限界。第二行到第三行是因为在最坏情况下T（n-1）=O(n2)，故1/nT(n-1)可被项O(n)吸收。,6.2 线性期望时间选择算法,我们用归纳法解上面的递归式。假设对满足递归式初始条件的某个常数c，有T(n)cn。将其代入我们刚才推导出来的式子：由这个归纳假设可得：,6.2 线性期望时间选择算法,因为我们可以选择足够大的c使得c(n/4+1/2)能支配O(n)项。总之，任意的顺序统计（尤其是中位数）平均
6、来说都可在线性时间内确定。,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)个
7、最小元素。,6.3最坏情况线性时间选择算法,二、SELECT算法图解 n个元素由小圆表示,每组占一个栏。各组的中数为白色，中数之中数x在图中标出。图中所画箭头是由较大元素指向较小的元素，从中可以看出每组五个元素中在x右边的三个大于x，在x左边的三个小于x。所有大于x的元素以阴影背景衬出。,6.3最坏情况线性时间选择算法,三、SELECT算法的运行时间分析第2步找出的中位数中，至少有一半大于x，除了那个所含元素可能少5的组和包含x的那个组之外。扣除这两组，所有大于x的元素数至少为：3（1/2 n/5-2）3n/10-6同理，小于x的元素至少有3n/10-6个。故在最坏情况下，第5步中至多有7n/
8、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+6n，且任何含80个或更多的元素的输入需要O（1）时间。这样可得递归式：,6.3最坏情况线性时间选择算法,通过归纳法我们可以证明此运行时间是线性的。假设对某常数c和所有的n80，有T(n)cn。将此归纳假设代到上面的递归式的右边，得：因为我们可以选择足够大的c，使对所有的n80，c(n/10-7)大于由O(n)项描述的函数。这就说明SELECT的最坏情况运行时间是线性的。,6.4 程序演示及说明,程序演示,作业,最坏情况线性时间的选择算法实现,The End,Thank you!,
