BFPRT算法（中位数之中位数）初窥 五

BFPRT算法的作者是5位真正的大牛（Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan），该算法入选了在StackExchange上进行的当今世界十大经典算法，而算法的简单和巧妙颇有我们需要借鉴学习之处。

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

当我们面对这一问题时，首先想到的直观方法一般为k次（假设k<n 2）选择排序，方法的伪码如下

function select(list[1..n], k)

     for i from 1 to k

         minIndex = i

         minValue = list[i]

         for j from i+1 to n

             if list[j] < minValue

                 minIndex = j

                 minValue = list[j]

         swap (list[i],list[minIndex])

     return list[k]

通过k次循环，方法可以依次选择出最小的k个值，该方法时间复杂度为O(kn)。当k较小时，方法的效率较为优秀，但当k->n/2时，方法复杂度变为了O(n^2)

思考该方法中多余的能量支出，方法按顺序输出了最小的k个元素，而这并不是我们需要的，如果我们只获得哪些值比该值小，而不对比其小的进行排序，算法代价将大幅下降。由于上面的方法用了选择排序的思想，那么利用快速排序的思想进行选择容易想到quickselection。

每次选择某一pivot，通过快速排序的思路，我们可以获得比pivot小的所有数和比其大的所有数，由此可以选出所需的kth值在哪以区间呢，并在该区间内再次使用quickselection。方法的伪码如下

function select(list, left, right, k)

     if left = right // If the list contains only one element

         return list[left]  // Return that element

     select pivotIndex between left and right

     pivotNewIndex := partition(list, left, right, pivotIndex)

     pivotDist := pivotNewIndex – left + 1

     if pivotDist = k

         return list[pivotNewIndex]

     else if k < pivotDist

         return select(list, left, pivotNewIndex - 1, k)

     else

         return select(list, pivotNewIndex + 1, right, k - pivotDist)

如quicksort一样，该方法在实际应用中有较好的效果，但在某些特殊情况中，由于pivot的选择，会出现一些效率极端不好的情况，例如某倒排表。

BFPRT是一种获得较优秀pivot的方法，方法的思路是使获得的pivot能够较为有效的对整个数据进行分割，并在其中利用寄存器的快速计算能力将问题拆分为代价极小的子问题。

方法的思路为：将元组分为n/5个5元的小数组，并对每组求中位数，在长度为n/5的序列中，求其中位数，该中位数的中位数保证了至少30%的数据在其一侧，由此保证了pivot的有效性（如图，改图来自wikipedia）

<a href="http://datasearch.ruc.edu.cn/~kaizhou/blog/wp-content/uploads/2011/05/9607d59b097fcd4c6b9a0fe1b0086c04.png"></a>

关于为何利用5作为小元组大小，我的想法是与寄存器的数量和运算有关。

由于pivot的有效分割和5元组中位数易求性，从n元组中取值的代价T(n)&lt;=T(n/5)+T(7n/10)+O(n)，T(n/5)是为中位数取中位数的时间，O(n)是遍历序列并求得中位数数列的时间.

设T(n)=cn,此处c可以不是常熟，若c与n成线性关系，则T(n)=O(n^2)，设遍历时间为an，a为常数

则有 T(n)&lt;=c(n/5)+c(7n/10)+an=c(9/10*n)+an //此处，低次已被省略低次项

求得C&lt;=10a 故c为常数，与n无关

且T(n)至少为O(n),

综上，该算法为一线性算法