BFPRT算法（TOP-K问题）

叁歲伎倆 2022-05-14 01:21 218阅读 0赞

#### 写在前面 ####

> n个数取最大的m个  
> BFPRT算法（中位数之中位数）  
> partion思想  
> 快速排序

#### 主要内容 ####

n个数值选出最大m个数（3<m<n）的最小算法复杂度是?
    O(n)
    O(nlogn)
    O(logn)
    O(mlogn)
    O(nlogm)
    O(mn)

我一开始选择的是nlogm。我想的是使用堆进行存储，开一个大小为m的堆将n个元素一个一个插入堆当中维护这个堆，每次插入的最大的复杂度为o(logm)，一共插入n次整体的复杂度为o(nlogm)。  
但是这还不是最快的方法。

> partion思想

可以采用和快速排序一样的思想，选取一个值将数组分成两部分，左边都是大于这个元素的右边都是小于这个元素的。这样就可以将数组分成两部分，当当前元素的位置大于m时说明应该递归左边的部分，如果小于m就递归右边的部分直到等于m。

在快速排序中，平均情况下数组被划分成相等的两部分，则时间复杂度为T(n)=2\*T(n/2)+O(n)，可以解得T(n)=nlogn。  
在快速选择中，平均情况下数组也是非常相等的两部分，但是只处理其中一部分，于是T(n)=T(n/2)+O(n)，可以解得T(n)=O(n)。但是二者在最坏情况下每次只能分出一个元素在某一边将导致每次问题的规模仅仅缩小一时间复杂度退化为o(n^2)。

> 对于快排来说我们不需要将所有的元素排好序，这属于多余的操作所以会带来不必要的复杂度。  
> 对于快速选择来说一次只会进入一半递归所以平均情况是o(n)但是对于主元的选择是决定算法效率的因素。

…

> BFPRT算法过程及代码

BFPRT算法步骤如下：  
（1）：选取主元；  
  （1.1）：将n个元素划分为⌊n/5⌋个组，每组5个元素，若有剩余，舍去；  
  （1.2）：使用插入排序找到⌊n/5⌋个组中每一组的中位数；  
  （1.3）：对于（1.2）中找到的所有中位数，调用BFPRT算法求出它们的中位数，作为主元；  
（2）：以（1.3）选取的主元为分界点，把小于主元的放在左边，大于主元的放在右边；  
（3）：判断主元的位置与k的大小，有选择的对左边或右边递归。

> 简单来说，就是将原始数据分成5组每组求一个中位数，这样求出n/5个中位数，对于这些中位数递归调用BFPRT算法求其中位数，以该中位数作为主元进行划分，再判断划分之后的位置进行下一次递归。

时间复杂度分析：  
BFPRT算法在最坏情况下的时间复杂度是O(n)，下面予以证明。  
首先将n个元素分成5个元素一组将分成n/5组，对于每一组的5个元素求出中位数，这里有n/5组，每组只有5个数无论采用什么样的方式5个数当中求出中位数的复杂度为o(1)，因为这里有n/5组，所以这里的复杂度为o(n)。  
对求出的这n/5个中位数递归调用BFPRT算法求其中位数的复杂度为T(n/5)，相同的问题规模是原来的5分之1。  
将得到的中位数作为下次partion的主元，此时对于partion进行分析：  
因为该主元是得到的n/5个中位数的中位数所以至少大于其中1/2个中位数，所以主元大于1/2 \* n/5 = n/10个中位数，每个中位数是原本5个元素当中的中位数所以每个中位数至少大于等于其中的3个数所以，我们选取的主元将至少大于等于n/10 \* 3= 3n/10个元素，同理也将小于等于3n/10个元素，这也就避免了最坏的区分。我们假设每次运气最差都是选择到的是7n/10的那个区域此时问题将缩小至T(7n/10)。

所以总体的时间复杂度为 ： T(n) = T(n/5) + T(7n/10) + O(n)  
计算可得： T(n) = 10O(n) = O(n)。