线性查找算法(BFPRT)

时间:2021-06-27 04:33:46

BFPRT算法的作者是5位真正的大牛(Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan)。

BFPRT解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。

步骤

  1. 将n个元素每 5 个一组,分成n/5(上界)组。
  2. 取出每一组的中位数,任意排序方法,比如插入排序。
  3. 递归的调用 selection 算法查找上一步中所有中位数的中位数,设为x,偶数个中位数的情况下设定为选取中间小的一个。
  4. 用x来分割数组,设小于等于x的个数为k,大于x的个数即为n-k。
  5. 若i==k,返回x;若i<k,在小于x的元素中递归查找第i小的元素;若i>k,在大于x的元素中递归查找第i-k 小的元素。

 终止条件:n=1 时,返回的即是i小元素。

================================
待查找的数组 :
4 1 2 56 24 5 6 97 8 0 4 8 6 2 3 6 1 9 3 4 6 2
找出第 8 小的数
被分割的数组 :
4 1 2 56 24
该数组的中位数 : 4
被分割的数组 :
5 6 97 8 0
该数组的中位数 : 6
被分割的数组 :
4 8 6 2 3
该数组的中位数 : 4
被分割的数组 :
6 1 9 3 4
该数组的中位数 : 4
中位数的集合 :
4 6 4 4
经过选择排序后的中位数数组 :
4 4 4 6
定义的 x 为 : 4
================================
待查找的数组 :
4 1 2 0 4 2 3 1 3 4 2
找出第 8 小的数 //数组长度比8大
被分割的数组 :
4 1 2 0 4
该数组的中位数 : 2
被分割的数组 :
2 3 1 3 4
该数组的中位数 : 3
中位数的集合 :
2 3
经过选择排序后的中位数数组 :
2 3
定义的 x 为 : 2 //前6小的数据已得出(0 1 1 2 2 2)
================================
待查找的数组 :
4 4 3 3 4
找出第 2 小的数 3 //(8-6=2 查出第二2小的数据)
第 8 小的数为 : 3
(0 1 1 2 2 2 3 3 4 4 4 5 6 6 6 6 8 8 9 24 56 97)

ps:

1.为何利用5作为元组大小,可能是与寄存器的数量和运算有关。

2.为何称为线性的解答:

划分时以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个数。