基本算法——BFPRT线性查找算法

作者 : 开心源码 本文共1117个字,预计阅读时间需要3分钟 发布时间: 2022-05-13 共267人阅读

    BFPRT算法处理的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分 析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想类似,当然,为使得算法在最坏情况下,仍然能达到o(n)的时间复杂 度,五位算法作者做了精妙的解决。

算法步骤:

1. 将n个元素每5个一组,分成n/5(上界)组。

2. 取出每一组的中位数,任意排序方法,比方插入排序。

3. 递归的调用selection算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。

4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。

5. 若i==k,返回x;若ik,在大于x的元素中递归查找第i-k小的元素。

终止条件:n=1时,返回的即是i小元素。

如上图所示,在第一步分出的所有组中,除了中位数的中位数(称为x)本身所在的组和元素少于5的组外,位于x后面的组,每组比x大或者者等于的元素个数为3,而在所有的中位数中,大于或者等于x的中位数至少一半,所以不算那两组,比x大或者者等于的数至少有: 

3{[1/2*(n/5)]-2} >= 3n/10-6

相似地,至少有3n/10 – 6个元素少于或者等于x,因而,在最坏的情况下,第5步中,算法的递归调用最多作用域7n/10 + 6个元素。 

假设算法的最坏情况的运行时间为T(n),步骤1、2、4需要O(n)的时间。(步骤2是对大小为O(1)的集合调用O(n)次快速排序。)步骤3所需要时间为T((n/5)),步骤5所需时间最多为T(7n/10 + 6)。假设T是单调递增的,得到如下递归式

证实对某个适当大的常数c和所有的n>0,有T(n)<=cn,以证实算法的运行时间是线性的。首先,假设对某个适当大的常数c和所有的n<140,有T(n)<=cn,假如c足够大,这个假设显然是成立的。同时,还要筛选一个常数a,使得对所有的n>0,上述公式中的O(n)项所对应的函数(用来形容算法运行时间中的非递归部分)有上界an。将这个归纳假设代入上述递归式的右边,得到: 

假如下式成立,上式最多是cn: 

当n>70时,上述不定式等价于不等式c >= 10a(n/(n-70))。由于假设n>=140,所以有n/(n-70)<=2。因而,选择c>=20a就能够满足不等式-cn/10+7c+an<=0。(注意,这里常数140并没有什么特别之处,我们可以用任何严格大于70的整数来替换它,而后再相应地选择c就可。)因而,最坏情况下算法的运行时间是线性的。 

参考 https://blog.csdn.net/maijia0754/article/details/77947167

说明
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是摆设,本站源码仅提供给会员学习使用!
7. 如遇到加密压缩包,请使用360解压,如遇到无法解压的请联系管理员
开心源码网 » 基本算法——BFPRT线性查找算法

发表回复