转载

BFPRT 算法（TOP-K 问题）

一：背景介绍

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

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

（1）快速排序的平均复杂度为$O(nlogn)$，但最坏时间复杂度为$O(n^2)$，不能始终保证较好的复杂度。

（2）我们只需要前$K$大的，而对其余不需要的数也进行了排序，浪费了大量排序时间。

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

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

（1）选取主元（首元素，尾元素或一个随机元素）；

（2）以选取的主元为分界点，把小于主元的放在左边，大于主元的放在右边；

（3）分别对左边和右边进行递归，重复上述过程。

而BFPRT算法主要是修改上述过程的第（1）步而已，接下来再看下BFPRT算法的过程。

二：BFPRT算法过程及代码

BFPTR算法过程：

（1）选取主元：

（1.1）将n个元素划分为$/frac n5$个组，每组5个元素，若有剩余，舍去；

（1.2）使用插入排序找到$/frac n5$个组中每一组的中位数；

（1.3）对于1.2中找到的中位数，递归进行步骤1.1和1.2，直至只剩下一个数，该数即作为主元；

（2）以选取的主元为分界点，把小于主元的放在左边，大于主元的放在右边；

（3）判断主元的位置与K的大小，有选择的对左边或右边递归。

接下来看下代码，代码所求为 前K小的数 ：

/**
 * BFPTR算法（前K小数问题）
 * 
 * author    刘毅（Limer）
 * date      2017/01/25
 * language  C++
 */

#include<iostream>
#include<algorithm>
using namespace std;

/* 对arry[left]...arry[right]进行插入排序（升序） */
void InsertSort(int arry[], int left, int right)
{
    for (int i = left + 1; i <= right; i++)
    {
        int j = i;
        while (j - 1 >= left&&arry[j] < arry[j - 1])  //j - 1 >= left避免数组越界
        {
            swap(arry[j - 1], arry[j]);
            j--;
        }
    }
}

/* 找到中位数的中位数，返回其下标 */
int FindMidMid(int arry[], int left, int right)
{
    if (right - left + 1 <= 5)  //如果不足5个
    {
        InsertSort(arry, left, right);
        return (left + right) >> 1;
    }

    int j = left - 1;
    for (int i = left; i <= right; i += 5)  //5个一组插入排序取中位数，并统一放在左侧
    {
        InsertSort(arry, i, i + 4);
        swap(arry[++j], arry[i + 2]);
    }

    return FindMidMid(arry, left, j);  //直至仅出现一个的中位数
}

/* 划分，pivot_index为划分基准的下标 */
int Partion(int arry[], int left, int right, int pivot_index)
{
    swap(arry[pivot_index], arry[right]);  //把基准放置右侧末尾

    int j = left;
    for (int i = left; i < right; i++)  //比基准小的都放在左侧
    {
        if (arry[i] <= arry[right])
            swap(arry[j++], arry[i]);
    }

    swap(arry[j], arry[right]);  //最后把基准换回来
    return j;
}

void BFPRT(int arry[], int left, int right, int k)
{
    if (left == right)
        return;
    int pivot_index = FindMidMid(arry, left, right);      //找到中位数的中位数的下标，其值作为基准
    int index = Partion(arry, left, right, pivot_index);  //以基准划分
    int num = index - left + 1;
    if (num == k)
        return;
    else if (num > k)
        BFPRT(arry, left, index - 1, k);
    else
        BFPRT(arry, index + 1, right, k - num);
}

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

    for (int i = 0; i < 10; i++)
        cout << arry[i] << " ";
    cout << endl;
    return 0;
}

三：时间复杂度分析

在此我们只讨论下该算法在最坏情况下的时间复杂度，开头已经说过，BFPRT算法即使在最坏情况下，其复杂度也是线性的，即O(n)，下面给予证明:

（1）InsertSort()，输入规模为常数5，以swap作基本操作，设其最坏情况下时间复杂度为$T_1$，则：

/begin{align}

T_1(n=5)&=1+2+3+4/tag{3.1.1}//

&=10/tag{3.1.2}//

&=/Theta(1)/tag{3.1.3}

/end{align}

（2）FindMidMid()，输入规模为n，以swap作基本操作，设其最坏情况下递归的时间复杂度为$T_2$，方程为：

/begin{align}

T_2(n)&=T_2(⌊/frac n5⌋)+⌊/frac n5⌋(T_1+1)+T_1/tag{3.2.1}//

&=T_2(/frac n5)+/frac n5(10+1)+10/tag{为方便计算，假设$n=5^t$，t为正整数}//

&=T_2(/frac n5)+/frac {11}5n+10/tag{$a=1,b=5,f(n)=/frac {11}5n+10$}//

&=n^{log_51}[T_2(1)+/sum_{j=1}^{log_5n}{(/frac {f(5^j)}{1^j})}]/tag{专栏首篇已给出证明}//

&=/frac {11}4n+10log_5n-/frac {11}4/tag{3.2.5}//

&</frac {11}4n+10n-/frac {11}4/tag{3.2.6}//

&=/frac {51}4n-/frac {11}4/tag{3.2.7}//

&=O(n)/tag{3.2.8}

/end{align}

（3）Partion()，输入规模为n，以swap为基础操作，得到的中位数x作为主元进行划分，为方便计算，我们依旧取$n=5^t$，t为正整数，在$/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}$的那一部分，设其最坏情况的时间复杂度为$T_3$：

/begin{align}

T_3(n)&=/frac {7n}{10}+2/tag{3.3.1}//

&=/Theta(n)/tag{3.3.2}

/end{align}

（4）BFPRT()，输入规模为n，以swap为基础操作，由第（3）分析，假如每次都选到了$/frac 7{10}$的那一部分，设其最坏情况下时间复杂度为$T_4$：

/begin{align}

T_4(n)&=T_4(/frac {7n}{10})+T_2(n)+T_3(n)/tag{3.4.1}//

&=T_4(/frac n{10/7})+cn/tag{c为某个正的常数}//

&=/sum_{j=1}^{log_{10/7}n}{c(/frac {10}7)^j}/tag{3.4.3}//

&=/frac {10c}3(n-1)/tag{3.4.4}//

&=O(n)/tag{3.4.5}

/end{align}

综上所得， BFPRT算法在最坏情况下的时间复杂度是O(n) 。

有的读者可能存在疑问，BFPRT算法为何选5作为分组，怎么不选3,4,6,7,8,9,...呢？

首先排除偶数，因为如果是偶数，我们很难取舍中位数，这个容易理解。

那奇数呢？如果是3，抛开递归前的操作不谈，FindMidMid()操作了$/frac n3$的数据，而最坏情况下Partion()操作了$/frac {2n}3$的数据，这就相当于一共操作了n个数据。而对于5而言，共操作了$/frac n5+/frac {7n}{10}=/frac {9n}{10}$。

那7呢？虽然它操作的数据总和比5小，但是这里不要忽略了插入排序的时间，由于插排的时间增大，式（3.2.7）中$/frac {51}4$处也增大，故而式（3.4.2）的$c$也增大。同理，9,11...皆不可。

参考文献：

[1] Thomas H.Cormen,etc. 算法导论（第三版）.

[2] Anany Levitin. 算法设计与分析基础（第三版）.

[3] . Median of medians . Wikipedia.

[4] ACdreamers. BFPRT 算法 .

[5] NOALGO. BFPRT算法 .

转自我的个人博客，原文为： http://www.61mon.com/index.php/archives/175/

原文 https://segmentfault.com/a/1190000008322873

正文到此结束