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算法（前K小数问题）
 *
 * author : 刘毅（Limer）
 * date   : 2017-01-25
 * mode   : C++
 */

#include <iostream>
#include <algorithm>

using namespace std;

/* 插入排序，返回中位数下标 */
int InsertSort(int array[], int left, int right)
{
    int temp;
    int j;

    for (int i = left + 1; i <= right; i++)
    {
        temp = array[i];
        j = i - 1;
        while (j >= left && array[j] > temp)
            array[j + 1] = array[j--];
        array[j + 1] = temp;
    }

    return ((right - left) >> 1) + left;
}

/* 返回中位数的中位数下标 */

int BFPRT(int array[], int left, int right, const int & k);

int GetPivotIndex(int array[], int left, int right)
{
    if (right - left < 5)
        return InsertSort(array, left, right);

    int sub_right = left - 1;

    for (int i = left; i + 4 <= right; i += 5)
    {
        int index = InsertSort(array, i, i + 4);  // 找到五个元素的中位数的下标
        swap(array[++sub_right], array[index]);   // 依次放在左侧
    }

    return BFPRT(array, left, sub_right, ((sub_right - left + 1) >> 1) + 1);
}

/* 利用中位数的中位数的下标进行划分，返回分界线下标 */
int Partition(int array[], int left, int right, int pivot_index)
{
    swap(array[pivot_index], array[right]);  // 把主元放置于末尾
    int divide_index = left;                 // 跟踪划分的分界线

    for (int i = left; i < right; i++)
    {
        if (array[i] < array[right])
            swap(array[divide_index++], array[i]);  // 比主元小的都放在左侧
    }

    swap(array[divide_index], array[right]);  // 最后把主元换回来

    return divide_index;
}

int BFPRT(int array[], int left, int right, const int & k)
{
    int pivot_index = GetPivotIndex(array, left, right);            // 得到中位数的中位数下标
    int divide_index = Partition(array, left, right, pivot_index);  // 进行划分，返回划分边界
    int num = divide_index - left + 1;

    if (num == k)
        return divide_index;
    else if (num > k)
        return BFPRT(array, left, divide_index - 1, k);
    else
        return BFPRT(array, divide_index + 1, right, k - num);
}

int main()
{
    int k = 5;
    int array[10] = { 1,1,2,3,1,5,-1,7,8,-10 };

    cout << "原数组：";
    for (int i = 0; i < 10; i++)
        cout << array[i] << " ";
    cout << endl;

    cout << "第" << k << "小值为：" << array[BFPRT(array, 0, 9, k)] << endl;

    cout << "变换后的数组：";
    for (int i = 0; i < 10; i++)
        cout << array[i] << " ";
    cout << endl;

    return 0;
}

100

101

/**

* BFPRT算法（前K小数问题）

* author : 刘毅（Limer）

* date : 2017-01-25

* mode : C++

#include <iostream>

#include <algorithm>

using namespace std;

/* 插入排序，返回中位数下标 */

int InsertSort(int array[], int left, int right)

{

int temp;

int j;

for (int i = left + 1; i <= right; i++)

{

temp = array[i];

j = i - 1;

while (j >= left && array[j] > temp)

array[j + 1] = array[j--];

array[j + 1] = temp;

}

return ((right - left) >> 1) + left;

}

/* 返回中位数的中位数下标 */

int BFPRT(int array[], int left, int right, const int & k);

int GetPivotIndex(int array[], int left, int right)

{

if (right - left < 5)

return InsertSort(array, left, right);

int sub_right = left - 1;

for (int i = left; i + 4 <= right; i += 5)

{

int index = InsertSort(array, i, i + 4); // 找到五个元素的中位数的下标

swap(array[++sub_right], array[index]); // 依次放在左侧

}

return BFPRT(array, left, sub_right, ((sub_right - left + 1) >> 1) + 1);

}

/* 利用中位数的中位数的下标进行划分，返回分界线下标 */

int Partition(int array[], int left, int right, int pivot_index)

{

swap(array[pivot_index], array[right]); // 把主元放置于末尾

int divide_index = left; // 跟踪划分的分界线

for (int i = left; i < right; i++)

{

if (array[i] < array[right])

swap(array[divide_index++], array[i]); // 比主元小的都放在左侧

}

swap(array[divide_index], array[right]); // 最后把主元换回来

return divide_index;

}

int BFPRT(int array[], int left, int right, const int & k)

{

int pivot_index = GetPivotIndex(array, left, right); // 得到中位数的中位数下标

int divide_index = Partition(array, left, right, pivot_index); // 进行划分，返回划分边界

int num = divide_index - left + 1;

if (num == k)

return divide_index;

else if (num > k)

return BFPRT(array, left, divide_index - 1, k);

else

return BFPRT(array, divide_index + 1, right, k - num);

}

int main()

{

int k = 5;

int array[10] = { 1,1,2,3,1,5,-1,7,8,-10 };

cout << "原数组：";

for (int i = 0; i < 10; i++)

cout << array[i] << " ";

cout << endl;

cout << "第" << k << "小值为：" << array[BFPRT(array, 0, 9, k)] << endl;

cout << "变换后的数组：";

for (int i = 0; i < 10; i++)

cout << array[i] << " ";

cout << endl;

return 0;

}

运行如下：

BFPRT 算法（TOP-K问题）

三：时间复杂度分析

四：参考文献

算法导论（第3版）. Page 120.

原文出处：刘毅

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

查看所有标签

猜你喜欢:

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

码农书籍

群体智能

James Kennedy、Russell C Eberhart、Yuhui Shi / 人民邮电出版社 / 2009-2-1 / 75.00元

群体智能是近年来发展迅速的人工智能学科领域.通过研究分散,自组织的动物群体和人类社会的智能行为, 学者们提出了许多迥异于传统思路的智能算法, 很好地解决了不少原来非常棘手的复杂工程问题.与蚁群算法齐名的粒子群优化(particle swarm optimization, 简称PSO)算法就是其中最受瞩目,应用最为广泛的成果之一. 本书由粒子群优化算法之父撰写,是该领域毋庸置疑的经典著作.作者......一起来看看《群体智能》这本书的介绍吧!

码农工具