《算法设计与分析-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!