BFPRT 算法(TOP-K问题)

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

内容简介:在一堆数中求其前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.


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

查看所有标签

猜你喜欢:

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

小米之道

小米之道

(美)克莱•舍基 / 张琪 / 浙江人民出版社 / 2017-10-1 / 49.90元

共享经济、自媒体预言者,“互联网先知”克莱·舍基,继《认知盈余》《人人时代》后,聚焦风口上的小米。资深科技商业观察家金错刀、润米咨询创始人刘润作序推荐。附多篇雷军内部讲话,详细解读成功完成“筑底”后小米的全新商业模式 纵观中国互联网发展史,可以明显发现,本土互联网企业的崛起,几乎都是先引入国外商业模式,然后通过强化本土化特点来构筑自己的壁垒。在这种背景下,小米是名副其实的新物种,它走的是相反......一起来看看 《小米之道》 这本书的介绍吧!

在线进制转换器
在线进制转换器

各进制数互转换器

SHA 加密
SHA 加密

SHA 加密工具

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

在线XML、JSON转换工具