BFPRT算法

标签: 算法 | 发表时间:2011-05-20 17:45 | 作者:Hins_pan zii
出处:http://hi.baidu.com/hins%5Fpan

BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处。

BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。

当我们面对这一问题时,首先想到的直观方法一般为k次(假设k
function select(list[1..n], k)
for i from 1 to k
minIndex = i
minValue = list[i]
for j from i+1 to n
if list[j] < minValue
minIndex = j
minValue = list[j]
swap (list[i],list[minIndex])
return list[k]

通过k次循环,方法可以依次选择出最小的k个值,该方法时间复杂度为O(kn)。当k较小时,方法的效率较为优秀,但当k->n/2时,方法复杂度变为了O(n^2)

思考该方法中多余的能量支出,方法按顺序输出了最小的k个元素,而这并不是我们需要的,如果我们只获得哪些值比该值小,而不对比其小的进行排序,算 法代价将大幅下降。由于上面的方法用了选择排序的思想,那么利用快速排序的思想进行选择容易想到quickselection。
每次选择某一pivot,通过快速排序的思路,我们可以获得比pivot小的所有数和比其大的所有数,由此可以选出所需的kth值在哪以区间呢,并在该区间内再次使用quickselection。方法的伪码如下
function select(list, left, right, k)
if left = right // If the list contains only one element
return list[left] // Return that element
select pivotIndex between left and right
pivotNewIndex := partition(list, left, right, pivotIndex)
pivotDist := pivotNewIndex – left + 1
if pivotDist = k
return list[pivotNewIndex]
else if k < pivotDist
return select(list, left, pivotNewIndex - 1, k)
else
return select(list, pivotNewIndex + 1, right, k - pivotDist)

如quicksort一样,该方法在实际应用中有较好的效果,但在某些特殊情况中,由于pivot的选择,会出现一些效率极端不好的情况,例如某倒排表。

BFPRT是一种获得较优秀pivot的方法,方法的思路是使获得的pivot能够较为有效的对整个数据进行分割,并在其中利用寄存器的快速计算能力将问题拆分为代价极小的子问题。
方法的思路为:将元组分为n/5个5元的小数组,并对每组求中位数,在长度为n/5的序列中,求其中位数,该中位数的中位数保证了至少30%的数据在其一侧,由此保证了pivot的有效性(如图,改图来自wikipedia)

关于为何利用5作为小元组大小,我的想法是与寄存器的数量和运算有关。
由于pivot的有效分割和5元组中位数易求性,从n元组中取值的代价T(n)<=T(n/5)+T(7n/10)+O(n),T(n/5)是为中位数取中位数的时间,O(n)是遍历序列并求得中位数数列的时间.
设T(n)=cn,此处c可以不是常熟,若c与n成线性关系,则T(n)=O(n^2),设遍历时间为an,a为常数
则有 T(n)<=c(n/5)+c(7n/10)+an=c(9/10*n)+an //此处,低次已被省略低次项
求得C<=10a 故c为常数,与n无关
且T(n)至少为O(n),
综上,该算法为一线性算法


类别:算法 查看评论

相关 [bfprt 算法] 推荐:

BFPRT算法

- zii - 小彰
BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan),该算法入选了在StackExchange上进行的当今世界十大经典算法,而算法的简单和巧妙颇有我们需要借鉴学习之处. BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度.

缓存算法

- lostsnow - 小彰
没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率. 我是LRU缓存算法,我把最近最少使用的缓存对象给踢走. 我总是需要去了解在什么时候,用了哪个缓存对象.

贪心算法

- Shan - 博客园-首页原创精华区
顾名思义,贪心算法总是作出在当前看来最好的选择. 也就是说贪心算法并不从整体最优考虑,它所作出的选择只是在某种意义上的局部最优选择. 当然,希望贪心算法得到的最终结果也是整体最优的. 虽然贪心算法不能对所有问题都得到整体最优解,但对许多问题它能产生整体最优解. 如单源最短路经问题,最小生成树问题等.

缓存算法

- 成 - FeedzShare
来自: 小彰 - FeedzShare  . 发布时间:2011年09月25日,  已有 2 人推荐. 没有人能说清哪种缓存算法由于其他的缓存算法. (以下的几种缓存算法,有的我也理解不好,如果感兴趣,你可以Google一下  ). 大家好,我是 LFU,我会计算为每个缓存对象计算他们被使用的频率.

K-Means 算法

- - 酷壳 - CoolShell.cn
最近在学习一些数据挖掘的算法,看到了这个算法,也许这个算法对你来说很简单,但对我来说,我是一个初学者,我在网上翻看了很多资料,发现中文社区没有把这个问题讲得很全面很清楚的文章,所以,把我的学习笔记记录下来,分享给大家. k-Means 算法是一种  cluster analysis 的算法,其主要是来计算数据聚集的算法,主要通过不断地取离种子点最近均值的算法.

查找算法:

- - CSDN博客推荐文章
从数组的第一个元素开始查找,并将其与查找值比较,如果相等则停止,否则继续下一个元素查找,直到找到匹配值. 注意:要求被查找的数组中的元素是无序的、随机的. 比如,对一个整型数组的线性查找代码:. // 遍历整个数组,并分别将每个遍历元素与查找值对比. 要查找的值在数组的第一个位置. 也就是说只需比较一次就可达到目的,因此最佳情况的大O表达式为:O(1).

排序算法

- - 互联网 - ITeye博客
排序算法有很多,所以在特定情景中使用哪一种算法很重要. 为了选择合适的算法,可以按照建议的顺序考虑以下标准: .     对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要.  一、冒泡(Bubble)排序——相邻交换 .  二、选择排序——每次最小/大排在相应的位置 .

联接算法

- - CSDN博客数据库推荐文章
本文摘自《锋利的SQL》: http://item.jd.com/10380652.html. 在Microsoft SQLServer Management Studio中执行查询时,如果选定工具栏中的 按钮,可以看到为查询生成的执行计划. 执行计划以图形方式显示了SQL Server查询优化器选择的数据检索方法,如表扫描、排序、哈希匹配等.

理解EM算法

- Chin - 我爱自然语言处理
EM(Expectation-Maximization)算法在机器学习和自然语言处理应用非常广泛,典型的像是聚类算法K-means和高斯混合模型以及HMM(Hidden Markov Model). 笔者觉得讲EM算法最好的就是斯坦福大学Andrew Ng机器学习课的讲课笔记和视频. 本文总结性的给出普遍的EM算法的推导和证明,希望能够帮助接触过EM算法但对它不是很明白的人更好地理解这一算法.

Memcached的LRU算法

- Eric - 平凡的世界
最近计划对Memcached做一些尝试性的改造,主要是针对Memcached在处理过期数据的时候进行改造,以实现在一个缓存的过期时间达到的时候,可以对该缓存的数据进行一个验证和存储的处理. 这个需求,主要是为了解决MySQL的写入瓶颈,通过延期、合并写入请求来减少MySQL的并发写入量. 现在逐渐记录出来和有需要的朋友一起讨论.