BFPRT算法

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

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

应用场景

线性时间内,从无序列表找到第 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。于是可以知道 xn 无关, 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