BFPRT 算法(TOP-K问题)

栏目: IT技术 · 发布时间: 6年前

内容简介:在一堆数中求其前k大或前k小的问题,简称TOP-K问题。

一:背景介绍

在一堆数中求其前k大或前k小的问题,简称TOP-K问题。而目前解决TOP-K问题最有效的算法即是”BFPRT算法”,又称为”中位数的中位数算法”,该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出,最坏时间复杂度为$O(n)$。

在首次接触TOP-K问题时,我们的第一反应就是可以先对所有数据进行一次排序,然后取其前k即可,但是这么做有两个问题:

  • 快速 排序 的平均复杂度为$O(nlogn)$,但最坏时间复杂度为$O(n^2)$,不能始终保证较好的复杂度。
  • 我们只需要前k大的,而对其余不需要的数也进行了排序,浪费了大量排序时间。

除这种方法之外,堆排序也是一个比较好的选择,可以维护一个大小为k的堆,时间复杂度为$O(nlogk)$。

那是否还存在更有效的方法呢?受到快速排序的启发,通过修改快速排序中主元的选取方法可以降低快速排序在最坏情况下的时间复杂度,并且我们的目的只是求出前k,故递归的规模变小,速度也随之提高。下面来简单回顾下快速排序的过程,以升序为例:

(1):选取主元(数组中随机一个元素);
(2):以选取的主元为分界点,把小于主元的放在左边,大于主元的放在右边;
(3):分别对左边和右边进行递归,重复上述过程。

二:BFPRT算法过程及代码

BFPRT算法步骤如下:

(1):选取主元;
(1.1):将n个元素划分为$⌊frac n5⌋$个组,每组5个元素,若有剩余,舍去;
(1.2):使用插入排序找到$⌊frac n5⌋$个组中每一组的中位数;
(1.3):对于(1.2)中找到的所有中位数,调用BFPRT算法求出它们的中位数,作为主元;
(2):以(1.3)选取的主元为分界点,把小于主元的放在左边,大于主元的放在右边;
(3):判断主元的位置与k的大小,有选择的对左边或右边递归。

上面的描述可能并不易理解,先看下面这幅图:

BFPRT 算法(TOP-K问题)

BFPRT()调用GetPivotIndex()和Partition()来求解第k小,在这过程中,GetPivotIndex()也调用了BFPRT(),即GetPivotIndex)和BFPRT()为互递归的关系。

下面为代码实现,其所求为前K小的数

运行如下:

BFPRT 算法(TOP-K问题)

三:时间复杂度分析

 

BFPRT 算法(TOP-K问题)

BFPRT 算法(TOP-K问题)

四:参考文献

  • 算法导论(第3版). Page 120.


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

群智能算法及其应用

群智能算法及其应用

高尚 / 中国水利水电出版社 / 2006-5 / 25.00元

《群智能算法及其应用》系统地描述了蚁群算法和粒子群优化算法的理论和实现技术及其应用,简单地介绍了鱼群算法。《群智能算法及其应用》着重强调各种算法的混合,讨论了蚁群算法与模拟退火算法的混合、蚁群算法与遗传算法的混合、蚁群算法与混沌理论混合、模拟退火算法、遗传算法与粒子群优化算法混合、混沌理论与粒子群优化算法的混合以及蚁群算法与粒子群优化算法的混合。书中还讨论了群智能算法在旅行商问题、武器一目标分配问......一起来看看 《群智能算法及其应用》 这本书的介绍吧!

HTML 编码/解码
HTML 编码/解码

HTML 编码/解码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HSV CMYK 转换工具
HSV CMYK 转换工具

HSV CMYK互换工具