BFPRT算法

发表于 | 分类于
字数统计: 821字 | 阅读时长 ≈ 4 分钟

BFPRT 算法

又称为 “中位数的中位数算法“，该算法由 Blum、Floyd、Pratt、Rivest、Tarjan 在1973年提出，最坏时间复杂度为 O(n)，最差的空间复杂度为O(logn)。

算法步骤

（1）：将 n 个元素划分为 ⌊n/5⌋ 个组，每组 5 个元素，若有剩余，舍去；
（2）：使用排序方法找到 ⌊n/5⌋ 个组中每一组的中位数；
（3）：对于（2）中找到的所有中位数，递归（1）（2）查找中位数的中位数，作为Partition划分过程的主元
（4）：进行Partition划分，即一次快排
（5）：判断主元的位置与 k 的大小，有选择的对左边或右边递归。

算法应用

BFPRT算法的一个经典应用就是TOP-K问题，即在一组数据中寻找第K大或第K小的元素。
这类问题可以分为对数据完全排序，部分排序和不排序。
完全排序情况下可以使用快速排序等排序方法能达到O(nlogn)的时间复杂度。
部分排序可以使用冒泡排序，选择排序等方法也能达到O(kn)的时间复杂度。
不排序的情况可以使用堆排序的方法，时间复杂度为O(nlogk)。
而BFPRT算法解决这类问题能达到O(n)的时间复杂度！！

实现代码

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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <iostream>
#include <algorithm>
using namespace std;
int array[]={1,12,3,4,1,5,2,7,8,88,5,2,32,1,35,-1,7,5,38,-11};

// 插入排序，返回中位数下标 
int insertSort(int left,int right){
	for(int i=left+1;i<=right;i++){
		int temp=array[i],j;
		for(j=i;j>left&&array[j-1]>temp;j--) array[j]=array[j-1];
		array[j]=temp;
	}
	return (left+right)>>1;
}

int BFPRT(int,int,int);

//返回中位数的中位数的下标
int getPivotIndex(int left,int right){
	if(right-left<5) return insertSort(left,right);
	int back=left-1;
	for(int i=left;i+4<right;i+=5){
		int index=insertSort(i,i+4);
		swap(array[++back],array[index]);
	}
	return BFPRT(left,back,((left+back)>>1)+1);
} 

//一趟快排 
int partition(int left,int right,int pivotIndex){
	swap(array[right],array[pivotIndex]);
	int mid=left;
	for(int i=left;i<right;i++){
		if(array[i]<array[right])
			swap(array[i],array[mid++]);
	}
	swap(array[right],array[mid]);
	return mid; 	
}

int BFPRT(int left,int right,int k){
	int pivotIndex=getPivotIndex(left,right);
	int mid=partition(left,right,pivotIndex);
	int count=mid-left+1;
	if(count==k){
		return mid;
	}else if(count>k){
		return BFPRT(left,mid-1,k);
	} else{
		return BFPRT(mid+1,right,k-count);
	}
} 

int main(){
	int k=5;
	int length=sizeof(array)/sizeof(array[0]);
	for(int i=0; i<length; i++) {
		cout<<array[i]<<"  ";
	}
	cout<<endl<<"第"<<k<<"小为："; 
	cout<<array[BFPRT(0,length-1,k)]<<endl;
	return 0;
}

算法复杂度分析

中位数的递归调用不超过最坏的线性情况，因为中位数列表是整个列表大小的20%，而其他的递归调用列表的最多70%，令T(n)为时间复杂度，则
这里写图片描述

  • T(2n/10)部分是查找⌊n/5⌋ 的中位数中的中位数，通过运行单独的Quickselect
  • T(7n/10)部分是实际的Quickselect递归
  • O(n) 部分 c·n 是创造分界，其中的一边递归进行Quickselect

使用归纳法，可以得到这里写图片描述

分析过程参考Median of medians