BFPRT算法

发表于 更新于 分类于 ， 阅读次数： 本文字数： 654 阅读时长 ≈ 2 分钟

BFPRT 算法是目前解决 TOP-K 问题最有效的算法，又称为中位数的中位数算法，该算法由 Blum、Floyd、Pratt、Rivest、Tarjan 提出，最坏时间复杂度为 \(O(n)\)。

在一堆数中求其前 k 大或前 k 小的问题，简称 TOP-K 问题。

BFPRT算法

应用场景

线性时间内，从无序列表找到第 k 小的元素。

基本思想

  • 首先把数组按 5 个数为一组进行分组，最后不足 5 个的忽略。对每组数进行排序（如插入排序）求取其中位数。
  • 把上一步的所有中位数移到数组的前面，对这些中位数递归调用 BFPRT 算法求得他们的中位数。
  • 将上一步得到的中位数作为划分的主元进行整个数组的划分。
  • 判断第 k 个数在划分结果的左边、右边还是恰好是划分结果本身，前两者递归处理，后者直接返回答案。

算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void bubble_sort(int* a, int left, int right){
    int tmp;
    for(int i=left; i<right; i++){
        for(int j=right; j>i; j--){
            if(a[j] < a[j-1]) tmp = a[j], a[j] = a[j-1], a[j-1] = tmp;
        }
    }
}

int partition(int* a, int left, int right, int baseIdx){
    int j = left - 1, tmp;
    //将基准放于数组尾部
    tmp = a[right], a[right] = a[baseIdx], a[baseIdx] = tmp;
    for(int i=left; i<right; i++){
        if(a[i] <= a[right]) tmp = a[i], a[i] = a[++j], a[j] = tmp;
    }
    tmp = a[right], a[right] = a[++j], a[j] = tmp;
    return j;
}

int bfprt(int* a, int left, int right, int k){
    if(right - left +1 <= 5){ //小于等于5个数，直接排序得到结果
        bubble_sort(a, left, right);
        return a[left + k -1];
    }
    int t = left - 1, tmp;  //t:当前替换到前面的中位数的下标
    for(int st = left, ed; (ed=st+4) <= right; st += 5){
        bubble_sort(a, st, ed);
        //将中位数替换到数组前面，便于递归求取中位数的中位数
        tmp = a[++t], a[t] = a[st+2], a[st+2] = tmp;
    }
    int baseIdx = (left + t) >> 1; //left到t的中位数的下标，作为主元的下标
    bfprt(a, left, t, baseIdx-left + 1); //不关心中位数的值，保证中位数在正确的位置
    int idx = partition(a, left, right, baseIdx), cur = idx - left + 1;
    if(k == cur) return a[idx];
    else if(k < cur) return bfprt(a, left, idx-1, k);
    else return bfprt(a, idx+1, right, k-cur);
}

复杂度分析

划分时以 5 个元素为一组求取中位数，共得到 n/5 个中位数，再递归求取中位数，复杂度为 T(n/5)。

得到的中位数 x 作为主元进行划分，在 n/5 个中位数中，主元 x 大于其中 1/2*n/5 = n/10 的中位数，而每个中位数在其本来的 5 个数的小组中又大于或等于其中的 3 个数，所以主元 x 至少大于所有数中的 n/10*3 = 3/10*n 个。同理，主元 x 至少小于所有数中的 3/10*n 个。即划分之后，任意一边的长度至少为 3/10，在最坏情况下，每次选择都选到了 7/10 的那一部分，则递归的复杂度为 T(7/10*n)。

在每 5 个数求中位数和划分的函数中，进行若干个次线性的扫描，其时间复杂度为 c*n，其中 c 为常数。其总的时间复杂度满足 T(n) <= T(n/5)+T(7/10*n)+c*n。

我们假设 T(n) = x*n ，其中 x 不一定是常数（比如 x 可以为 n 的倍数，则对应的 T(n) = O(n^2))。则有 x*n <= x*n/5+x*7/10*n+c*n，得到 x <= 10*c。于是可以知道 x 与 n 无关， T(n) <= 10*c*n，为线性时间复杂度算法。而这又是最坏情况下的分析，故 BFPRT 可以在最坏情况下以线性时间求得 n 个数中的第 k 个数。

References

https://en.wikipedia.org/wiki/Median_of_medians

https://www.cnblogs.com/informatics/p/5092741.html