《算法设计与分析-9顺序统计学》由会员分享，可在线阅读，更多相关《算法设计与分析-9顺序统计学（17页珍藏版）》请在金锄头文库上搜索。
1、算法设计与分析谭守标 安徽大学 电子学院 2007.9第六章 顺序统计学n顺序统计的概念n线性期望时间选择算法（过程及分析）n最坏情况线性时间选择算法（过程及分 析）n程序演示及说明6.1 顺序统计的概念一、顺序统计1、顺序统计的概念：一个由n个元素组成的 集合的第i个顺序统计就是该集合中第i小的元 素。例如，一个集合元素中的最小值即其第 一个顺序统计（i=1）；最大值即为其第n个 顺序统计（i=n）。2、中位数的概念：一个中位数非正式的说即 该集合的“中间点”上的元素。6.2 线性期望时间选择算法一、选择问题的定义1、输入：一个含n个（不同的）数的集合A和一个数 i， 1 in。2、输出：恰
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比较就可以确定最小值 。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
3、 then return 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.平均情况分析 因为是一个随机化过程,所以没有一个特别的输入会 导致最坏性态的发生，所以分析该算法的平均情况性能 很有实际意义，通过分析我们会发现该算法的平均情况
4、性能较好。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） 6.2 线性期望时间选择算法上面推导中由第一行到第二行是因为max(1,n-1)=n-1 ，且如果n是奇数，每一项T（n/
5、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(n2)，故1/nT(n-1)可被项O(n)吸收。6.2 线性期望时间选择算法我们用归纳法解上面的递归式。假设对满足递归式 初始条件的某个常数c，有T(n) cn。将其代入我们刚 才推导出来的式子：由这个归纳假设可得：6.2 线性期望时间选择算法因为我们可以选择足够大的c使得 c(n/4
6、+1/2)能支配O(n)项。总之，任意的顺序统计（尤其是中位数） 平均来说都可在线性时间内确定。6.3最坏情况线性时间选择算法一、SELECT算法的基本步骤 1、将输入数组的n个元素划分成n/5组，每组5个元素 ，且至多只有一个组包含余下的n mod 5个有元素 (如 图）。 2、通过插入排序来找出每组中的中位数，并取其中间 元素。（如果某组中有偶数个元素，则取两个中位数中 较大者。） 3、对第二步中找出的n/5个中位数，递归调用 SELECT以找出其中位数x。 4、用修改的PARTITION版本、按x来对输入数组进行划 分。设k为划分的低区中的元素数，则(n-k)为高区中的 元素数。 5、若
7、ik，则在低区递归调用SELECT以找出第i小的元 素；否则，若ik，则在高区找第（i-k)个最小元素。6.3最坏情况线性时间选择算法二、SELECT算法图解n个元素由小圆表示,每组占一个栏。各组的中数为 白色，中数之中数x在图中标出。图中所画箭头是由较 大元素指向较小的元素，从中可以看出每组五个元素中 在x右边的三个大于x，在x左边的三个小于x。所有大于 x的元素以阴影背景衬出。6.3最坏情况线性时间选择算法三、SELECT算法的运行时间分析 第2步找出的中位数中，至少有一半大于x，除了那 个所含元素可能少5的组和包含x的那个组之外。扣除这 两组，所有大于x的元素数至少为： 3（1/2 n/
8、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的 最坏情况运行时间是线性的。6.4 程序演示及说明程序演示作业n最坏情况线性时间的选择算法实现The EndnThank you!
