BFPRT 算法(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()调用GetPivotIndex()和Partition()来求解第k小,在这过程中,GetPivotIndex()也调用了BFPRT(),即GetPivotIndex)和BFPRT()为互递归的关系。

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

运行如下:

三:时间复杂度分析

 

QQ截图20171024111911

QQ截图20171024112045

四:参考文献

  • 算法导论(第3版). Page 120.
2 3 收藏 2 评论

相关文章

可能感兴趣的话题



直接登录
最新评论
  • 梧桐   10/25

    直接利用快排思想不就完了吗,分组干什么?

    假如我们要求top 5小。快排跑一趟的结果是我们选取的pivot这个数所处的位置一定就是最终排完序的位置,假设这个位置为j,而且pivot左边的数都小于它,右边的数都大于它。

    if j == 5,那直接结束了,pivot左边的数都是top 5。

    if j > 5, 表示top 5全在左边,那左边再跑快排,一直到某一趟pivot的位置恰好等于5。

    这个比快排省掉的就是只需要单侧递归

  • LR2SD java工程师 10/30

    可以考虑堆排序啊,假如top10大,维护一个最大堆size为10,把所有的元素都在堆中,这样的时间复杂度为O(NlogM)。

跳到底部
返回顶部