BFPRT 算法（TOP-K 问题）

时间  2019-11-10 标签 bfprt 算法 k 问题
原文连接： https://subetter.com/algorith...

一：背景介绍

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

在首次接触TOP-K问题时，咱们的第一反应就是能够先对全部数据进行一次排序，而后取其前k便可，可是这么作有两个问题：ios

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

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

那是否还存在更有效的方法呢？咱们来看下BFPRT算法的作法。算法

在快速排序的基础上，首先经过判断主元位置与k的大小使递归的规模变小，其次经过修改快速排序中主元的选取方法来下降快速排序在最坏状况下的时间复杂度。数组

下面先来简单回顾下快速排序的过程，以升序为例：函数

  1. 选取主元；
  2. 以选取的主元为分界点，把小于主元的放在左边，大于主元的放在右边；
  3. 分别对左边和右边进行递归，重复上述过程。

二：算法过程及代码

BFPRT算法步骤以下：spa

  1. 选取主元；
    1.1. 将n个元素按顺序分为$⌊\frac n5⌋$个组，每组5个元素，如有剩余，舍去；
    1.2. 对于这$⌊\frac n5⌋$个组中的每一组使用插入排序找到它们各自的中位数；
    1.3. 对于 1.2 中找到的全部中位数，调用BFPRT算法求出它们的中位数，做为主元；
  2. 以 1.3 选取的主元为分界点，把小于主元的放在左边，大于主元的放在右边；
  3. 判断主元的位置与k的大小，有选择的对左边或右边递归。

上面的描述可能并不易理解，先看下面这幅图：3d

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

下面为代码实现，其所求为前k小的数：htm

#include <iostream>
#include <algorithm>

using namespace std;

int InsertSort(int array[], int left, int right);
int GetPivotIndex(int array[], int left, int right);
int Partition(int array[], int left, int right, int pivot_index);
int BFPRT(int array[], int left, int right, int k);

int main()
{
    int k = 8; // 1 <= k <= array.size
    int array[20] = { 11,9,10,1,13,8,15,0,16,2,17,5,14,3,6,18,12,7,19,4 };

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

    // 由于是以 k 为划分，因此还能够求出第 k 小值
    cout << "第 " << k << " 小值为：" << array[BFPRT(array, 0, 19, k)] << endl;

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

    return 0;
}

/**
 * 对数组 array[left, right] 进行插入排序，并返回 [left, right]
 * 的中位数。
 */
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];
            j--;
        }
        array[j + 1] = temp;
    }

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

/**
 * 数组 array[left, right] 每五个元素做为一组，并计算每组的中位数，
 * 最后返回这些中位数的中位数下标（即主元下标）。
 *
 * @attention 末尾返回语句最后一个参数多加一个 1 的做用其实就是向上取整的意思，
 * 这样能够始终保持 k 大于 0。
 */
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]);
    }

    // 利用 BFPRT 获得这些中位数的中位数下标（即主元下标）
    return BFPRT(array, left, sub_right, ((sub_right - left + 1) >> 1) + 1);
}

/**
 * 利用主元下标 pivot_index 进行对数组 array[left, right] 划分，并返回
 * 划分后的分界线下标。
 */
int Partition(int array[], int left, int right, int pivot_index)
{
    swap(array[pivot_index], array[right]); // 把主元放置于末尾

    int partition_index = left; // 跟踪划分的分界线
    for (int i = left; i < right; i++)
    {
        if (array[i] < array[right])
        {
            swap(array[partition_index++], array[i]); // 比主元小的都放在左侧
        }
    }

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

    return partition_index;
}

/**
 * 返回数组 array[left, right] 的第 k 小数的下标
 */
int BFPRT(int array[], int left, int right, int k)
{
    int pivot_index = GetPivotIndex(array, left, right); // 获得中位数的中位数下标（即主元下标）
    int partition_index = Partition(array, left, right, pivot_index); // 进行划分，返回划分边界
    int num = partition_index - left + 1;

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

运行以下：

原数组：11 9 10 1 13 8 15 0 16 2 17 5 14 3 6 18 12 7 19 4
第 8 小值为：7
变换后的数组：4 0 1 3 2 5 6 7 8 9 10 12 13 14 17 15 16 11 18 19

三：时间复杂度分析

BFPRT算法在最坏状况下的时间复杂度是$O(n)$，下面予以证实。令$T(n)$为所求的时间复杂度，则有：

$$ T(n)≤T(\frac n 5)+T(\frac {7n}{10})+c⋅n\tag{c为一个正常数} $$

其中：

  • $T(\frac n 5)$来自GetPivotIndex()，n个元素，5个一组，共有$⌊\frac n5⌋$个中位数；
  • $T(\frac {7n}{10})$来自BFPRT()，在$⌊\frac n5⌋$个中位数中，主元x大于其中 $\frac 12⋅\frac n5=\frac n{10}$的中位数，而每一个中位数在其原本的5个数的小组中又大于或等于其中的3个数，因此主元x至少大于全部数中的$\frac n{10}⋅3=\frac {3n}{10}$个。即划分以后，任意一边的长度至少为$\frac 3{10}$，在最坏状况下，每次选择都选到了$\frac 7{10}$的那一部分。
  • $c⋅n$来自其它操做，好比InsertSort()，以及GetPivotIndex()和Partition()里所需的一些额外操做。

设$T(n)=t⋅n$，其中t为未知，它能够是一个正常数，也能够是一个关于n的函数，代入上式：

$$ \begin{align} t⋅n&≤\frac {t⋅n}5+\frac{7t⋅n}{10}+c⋅n \tag{两边消去n}\\ t&≤\frac t 5+\frac {7t}{10}+c \tag{再化简}\\ t&≤10c \tag{c为一个正常数} \end{align} $$

其中c为一个正常数，故t也是一个正常数，即$T(n)≤10c⋅n$，所以$T(n)=O(n)$，至此证实结束。

接下来咱们再来探讨下BFPRT算法为什么选5做为分组主元，而不是2, 3, 7, 9呢？

首先排除偶数，对于偶数咱们很难取舍其中位数，而奇数很容易。再者对于3而言，会有$T(n)≤T(\frac n 3)+T(\frac {2n}3)+c⋅n$，它自己仍是操做了n个元素，与以5为主元的$\frac {9n}{10}$相比，其复杂度并无减小。对于7，9，...而言，上式中的10c，其总体都会增长，因此与5相比，5更适合。

四：参考文献

联系我们 沪ICP备2021010478号-7