精华内容
下载资源
问答
  • BFPRT

    2020-03-12 02:08:28
    BFPRT 题目:在一个无序数组中找到一个第K小的数 一:背景介绍 原文链接: https://segmentfault.com/a/1190000008322873 在一堆数中求其前 k 大或前 k 小的问题,简称 TOP-K 问题。而目前解决 TOP-K 问题最有效的...

    BFPRT

    题目:在一个无序数组中找到一个第K小的数

    一:背景介绍

    原文链接: https://segmentfault.com/a/1190000008322873

    在一堆数中求其前 k 大或前 k 小的问题,简称 TOP-K 问题。而目前解决 TOP-K 问题最有效的算法即是 BFPRT 算法,又称为中位数的中位数算法,该算法由 Blum、Floyd、Pratt、Rivest、Tarjan 提出,最坏时间复杂度为 O(N*logk)。

    在首次接触 TOP-K 问题时,我们的第一反应就是可以先对所有数据进行一次排序,然后取其前 k 即可,但是这么做有两个问题:

    1. 快速排序的平均复杂度为 O(N*logN),但最坏时间复杂度为O(N^2),不能始终保证较好的复杂度;
    2. 我们只需要前 k 大的,而对其余不需要的数也进行了排序,浪费了大量排序时间。

    除这种方法之外,堆排序也是一个比较好的选择,可以维护一个大小为 k 的堆。

    那是否还存在更有效的方法呢?我们来看下 BFPRT 算法的做法。

    在快速排序的基础上,首先通过判断主元位置与k的大小使递归的规模变小,其次通过修改快速排序中主元的选取方法来降低快速排序在最坏情况下的时间复杂度

    下面先来简单回顾下快速排序的过程,以升序为例:

    1. 选取主元;
    2. 以选取的主元为分界点,把小于主元的放在左边,大于主元的放在右边;
    3. 分别对左边和右边进行递归,重复上述过程。

    二:算法过程及代码

    1. 选取主元

      • 将数组中的 n 个元素按顺序分为多个组,每组5个元素, 不足5个,自成一组
      • 使用插入排序,分别求这几个组的中位数,求的过程中把每一组的中位数依次放在数组的前面
        比如数组总共有25个元素,这一步结束,数组前五个元素分别为5个组的中位数。
      • 然后使用BFPRT算法从放于数组前端的中位数中选取中位数,此数值即为主元。返回此数值的下标,而不是值。
    2. 以 1.3 选取的主元为分界点进行划分,把小于主元的放在左边,大于主元的放在右边 。划分完成后,返回主元的下标,即等于区域的右边界。

    3. 判断主元的位置与 k 的大小,如果主元的下标恰好等于K,则该主元就是第k小的元素,否则,有选择的对左边或右边递归。

    注意

    • BFPRT算法和代码中的插入排序算法,返回的都是下标。
    • 第K小的元素,K值不能为0,所以在写代码的过程中要保证K>0

    三:代码(JAVA)

    class Solution_BFPRT{
    
        /**
         * 返回数组 arr[left, right] 的第 k 小数的下标
         */
        public static int bfprt(int[] arr, int left, int right, int k){
            //将数组划分成N/5份,然后找这N/5个中位数中的中位数,把它当做划分点
            int pivot = getPivotIndex(arr, left, right);
            //根据pivot,将数组划分成三个区域,返回等于区域的右边界
            int index = partition(arr, left, right, pivot);
            //下标从left到index之间,总共有left_num个数
            int left_num = index - left + 1;
            if(left_num == k){//如果下标从left到index之间刚好有k个数,则index为第k小的数的下标
                return index;
            }else if(left_num > k){//否则,接着划分
                return bfprt(arr, left, index - 1, k);
            }else{
                return bfprt(arr, index + 1, right, k - left_num);
            }
        }
    
        //将数组划分成N/5份,然后找这N/5个中位数中的中位数
        public static int getPivotIndex(int[] arr, int left, int right){
            int len = right - left + 1;
            if(len <= 5){
                return insertSort(arr, left, right);
            }
            int i = left, j = left - 1;
            while(i + 4 <= right){
                int index = insertSort(arr, i, i + 4);
                //将该5个数中的中位数,放到arr数组的前面。
                swap(arr, index, ++j);
                i += 5;
            }
            //以上操作完成后,数组[left,j]区间上的数为每一个小数组的中位数。使用BFPRT算法再求中位数的中位数,是为了降低时间复杂度。
            //最后一个参数多加一个 1 的作用其实就是向上取整的意思,这样可以始终保持 k 大于 0。
            //因为数组中第k小的元素,k的值是从1开始的
            return bfprt(arr, left, j, (j - left + 1) / 2 + 1);
        }
    
        /*
         * k为主元的下标,以下标k的元素值,进行一次划分,将数组划分成三个区域
         * 返回等于区域的右边界
         * */
        public static int partition(int[] arr, int left, int right, int k){
            swap(arr, right, k);
            int less = left - 1;
            int more = right;
            int pivot = arr[right];
            int cur = left;
            while(cur < more){
                if(arr[cur] < pivot){
                    swap(arr, ++less, cur++);
                }else if(arr[cur] > pivot){
                    swap(arr, --more, cur);
                }else{
                    cur++;
                }
            }
            swap(arr, cur, right);
            return cur;
        }
    
        //使用插入排序找数组的中位数的下标
        public static int insertSort(int[] arr, int left, int right){
            int mid = (left + right) / 2;
            for(int i = left + 1; i <= right; i++){
                for(int j = i; j > left && arr[j] < arr[j - 1]; j--){
                    swap(arr, j, j - 1);
                }
            }
            return mid;//返回下标。
        }
    
        public static void swap(int[] arr, int a, int b){
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    
        public static void main(String[] args) {
            int[] arr = new int[]{1,2,3,4,5,   6,8,7,9,10,   1,6,8,4,9,   2,5,4,9,6,   3,4,7,8,1};
            //使用bfprt算法获取第k小的元素的下标
            int index = bfprt(arr, 0, arr.length - 1, 10);
            //则第k小的元素的值为arr[index],此时arr数组中的顺序已经被更改。
            System.out.println(arr[index]);
        }
    }
    

    时间复杂度O(N)

    请看:https://segmentfault.com/a/1190000008322873

    展开全文
  • bfprt

    2018-11-15 19:39:36
    摘要: BFPRT 算法:1973 年, Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan 集体出动,合写了一篇题为 “Time bounds for selection” 的论文,给出了一种在数组中选出第 k 大元素的算法,俗称"中位数之中位数...

    摘要: BFPRT 算法:1973 年, Blum 、 Floyd 、 Pratt 、 Rivest 、 Tarjan 集体出动,合写了一篇题为 “Time bounds for selection” 的论文,给出了一种在数组中选出第 k 大元素的算法,俗称"中位数之中位数算法"。依靠一种精心设计的 pivot 选取方法,该算法从理论上保证了最坏情形下的线性时间复杂度,打败了平均线性、最坏 O(n^2) 复杂度的传统算法。一群大牛把递归算法的复杂度分析玩弄于股掌之间,构造出了一个当之无愧的来自圣经的算法。

    参考: http://en.wikipedia.org/wiki/Median_of_medians

    算法步骤:

    1. 将 n 个元素每 5 个一组,分成 n/5 (上界)组。

    2. 取出每一组的中位数,任意排序方法,比如插入排序。

    3. 递归的调用 select 算法查找上一步中所有中位数的中位数,设为 x,偶数个中位数的情况下设定为选取中间小的一个。

    4. 用 x 来分割数组,设小于等于 x 的个数为 m ,大于 x 的个数即为 n-m。

    5. 若 k==m,返回 x;若 k<m,在小于 x 的元素中递归查找第 k 小的元素;若 k>m,在大于 x 的元素中递归查找第 k-m 小的元素。

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

    性能分析:

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

    我参考别人的代码,加了一点自己理解的注释

    #include <iostream>
    using namespace std;

    void swap(int *array, int s,int e)
    {
        int temp;
        temp = array[s];
        array[s] = array[e];
        array[e] = temp;
    }

    // BFPRT: 在数组中寻找第 k 小元素(Top k)
    /************************************************************************
    FindKthSmallest(Array, k)
    pivot = some pivot element of the array.
    L = Set of all elements smaller than pivot in Array
    R = Set of all elements greater than pivot in Array
    if |L| > k FindKthSmalles(L, k)
    else if(|L|+1 == k) return pivot
    else return FindKthSmallest(R, k-|L|+1)
    ************************************************************************/

    void insertsort(int *array_t, int start, int end)
    {
        for (int i = start; i <= end; i++) {
            int inserted_data = array_t[i];
            int j = i;
            for (; j > start && inserted_data < array_t[j - 1]; j--) {
                    array_t[j] = array_t[j - 1];
            }
            if (j != i) {
                array_t[j] = inserted_data;        
            }
        }
    }

    int partition(int *array_t, int low, int high, int pivot_index)
    {
        int pivot_value = array_t[pivot_index];
        swap(array_t, low, pivot_index);
        while (low < high) {
            while (low < high && array_t[high] >= pivot_value) {
                high--;
            }
            if (low < high) {
                array_t[low++] = array_t[high];
            }
            while (low < high && array_t[low] <= pivot_value) {
                low++;
            }
            if (low < high) {
                array_t[high--] = array_t[low];
            }
        }
        array_t[low] = pivot_value;
        return low;
    }

    // 五划分中项:中位数的中位数(the median of medians algorithm)
    // Return the kth value
    int select(int *array_t, int left, int right, int k)
    {
        const int k_group_size = 5;
        int size = right - left + 1;
        if (size <= k_group_size) {
            insertsort(array_t, left, right);
            return array_t[k + left - 1];
        }
        // (right - left) / 2 + left
        const int num_group = (size % k_group_size) > 0 ? (size / k_group_size) + 1 : (size / k_group_size);

        for (int i = 0; i < num_group; i++) {
            int sub_left = left + i * k_group_size;
            int sub_right = sub_left + k_group_size - 1;
            if (sub_right > right) {
                sub_right = right;
            }
            insertsort(array_t, sub_left, sub_right);
            // IMPORTANT !!
            // Place these median in front of array_t, so as to recurse to find the median of median
            int median = sub_left + ((sub_right - sub_left) >> 1);
            swap(array_t, left + i, median);
        }

        // Get the index of median
        int pivot_index = left + ((num_group - 1) >> 1);

        // Recurse to call and place the median on the pivot_index, without care about the median value
        // Because the value of pivot_index must be the median after select function recursive call.
        /*
            //k = (num_group + 1) >> 1 中位数 防止k=0,所以num_group+1
        //int select(int *array_t, int left, int right, int k)
        {
        const int k_group_size = 5;
        int size = right - left + 1;
        if (size <= k_group_size) {
            insertsort(array_t, left, right);
            return array_t[k + left - 1];                //k + left - 1=(num_group+1)/2 + left -1=num_group/2 + left - 1/2 中位数
        }*/
        select(array_t, left, left + num_group - 1, (num_group + 1) >> 1);
        int mid_index = partition(array_t, left, right, pivot_index);
        int _ith = mid_index - left + 1;
        // _ith_element == array_t[_ith]
        if (k == _ith) {
            return array_t[mid_index];
        } else if (k < _ith) {
            return select(array_t, left, mid_index - 1, k);
        } else {
            return select(array_t, mid_index + 1, right, k - _ith);
        }
    }

    int main()
    {
        int k = 8; // 1 <= k <= array.size
        int array[20] = { 11,9,10,1,13,8,15,0,16,2,17,5,14,3,6,18,12,7,19,4 };

        cout << "原数组:";
        for (int i = 0; i < 20; i++)
            cout << array[i] << " ";
        cout << endl;

        // 因为是以 k 为划分,所以还可以求出第 k 小值
        cout << "第 " << k << " 小值为:" << array[select(array, 0, 19, k)] << endl;

        cout << "变换后的数组:";
        for (int i = 0; i < 20; i++)
            cout << array[i] << " ";
        cout << endl;

        return 0;
    }

     


    展开全文
  • BFPRT算法

    2019-12-19 16:53:29
    问题引入 希望你可以在一个无序数组中找到第k小的数,开始你的表演。 方法1:我们可以采取...虽然他不是BFPRT,但是已经足够优秀了。时间复杂度是基于概率的,长期的期望可以做到O(N),最好O(N),最差的时候为O(N^...

    问题引入

    希望你可以在一个无序数组中找到第k小的数,开始你的表演。
    方法1:我们可以采取排序的方式,但是这样就会产生一个O(NlogN)的代价。
    方法2:我们可以采取partation的过程,如果命中直接返回,否则看目标值在哪个区域,再次partition(快拍的改进)。虽然他不是BFPRT,但是已经足够优秀了。时间复杂度是基于概率的,长期的期望可以做到O(N),最好O(N),最差的时候为O(N^2)(每次值搞定一个数),就像是选择排序一样。最好情况下,即每次选择划分值都能落在最中间。那么时间复杂度的表达式T(N)=T(N/2)+O(N)。应用master公式我们可以得到其时间复杂度是O(N)的。
    方法3:我们可以使用BFPTR算法,这样可以做到时间复杂度严格的O(N),与概率无关。

    BFPRT算法

    BFPRT算法与第二种算法的差别就在划分值的选择策略上。剩余的东西与方法2一样的。

    步骤

    1. 将所有的数据按照5个一组,不满5个的另作一组,进行分组。O(1)。
    2. 对每个小组内5个元素进行排序,每个小组排序的时间复杂度是O(1),有N/5个组,所以时间复杂度是O(N)的。
    3. 拿每个数组的中位数出来作为一个新数组new_arr。长度是N/5的。(O(N))
    4. 递归调用BFPRT算法,参数为new_arr(N/5),要查找的数为中位数,正好是数组一半的第k小的数。然后用返回值作为划分值。至少有3/10的数比他大,最多有7/10的数比你多。。同理,至少有3/10的数比他小。T(N/5)
    5. 用返回值进行partition。O(N)
    6. 如果命中直接返回,如果没有命中,走左边还是走右边。T(7N/10)。

    疑问

    1.为什么在步骤1中选择5个数作为一组?

    其实你可以选择 3个、7个或者9个,选择的数字的个数不同其实就是在搞复杂度的表达式,如果我们选择的数字个数使得复杂度不能收敛到O(N),那么就不能选择。外传:因为BFPRT算法的发明者有5个人并且因为5可以使得复杂度表达式收敛到O(N)上。

    2.为什么你在步骤2中对于5个数进行排序的时候为什么可以说时间复杂度是O(1)的?

    因为我们只有5个数啊。数据量很小,此时使用插入排序可以做到很快。

    3.为什么在步骤4中,你说一定有至少有3/10的数比他大,最多有7/10的数比你多?

    这里这个3/10是与我们选择几个数作为一组是有关的,如果选择5个数作为一组,那么我们会得到下面这样的一张图。

    在这里插入图片描述
    我们选择出每组中的中位数(5,7,6,5,3),然后排序得到其中位数(5),由于5是中位数,所以在这组选择出来的数据中,一定有1/2比该数大(总体数据的1/10),然后将这1/2放会到原来的数组中,那么又有两个数比选择出来的数大,这样就多出了2/10的数据,总体加起来就是3/10这个魔数了

    4. 为什么步骤6中出现了一个7/10这个魔术?他有什么含义?

    7/10这个魔数同样是因为我们选择了5个数作为一组,那么至少有3/10的数据比我们的划分值小,也就是说最多有7/10的数据比我们的划分值大,由于在复杂度的计算的过程中,我们计算的是最差时间复杂度,所以就有了7/10这个魔数。

    时间复杂度的计算

    最坏情况下:T(N) = T(N/5)+ T(7N/10)+O(N) = O(N)。所以BFPRT算法在最差的情况下也能O(N)。

    应用

    1. 在一个数组中找到最小的第k个数,我们可以使用堆,但是这样是O(NlogN)的。
    2. 最优解是BFPRT,如果找出了第k小的数,那么前k个就好找了(要求无重复),通过遍历。

    示例代码

    方法1:

    int findLastK0(const vector<int> &vec, int kTh)
    {
    	if (vec.size() == 0 || kTh > vec.size() || kTh < 1)
    	{
    		throw exception("I can't do it");
    	}
    	vector<int> myCopy(vec);
    	sort(myCopy.begin(),myCopy.end());
    
    	return myCopy[kTh-1];
    }
    

    方法2

    vector<int> partition(vector<int> &vec,int left, int right)
    {
    	int size = vec.size();
    	//swap(vec[rand() % size], vec[size - 1]);
    	int more = right;
    	int less = left-1;
    	while (left < more)
    	{
    		if (vec[left] < vec[right])
    		{
    			swap(vec[left++], vec[++less]);
    		}
    		else if (vec[left] > vec[right])
    		{
    			swap(vec[left], vec[--more]);
    		}
    		else
    		{
    			++left;
    		}
    	}
    	swap(vec[more], vec[right]);
    	return vector<int>{less + 1, more};
    }
    
    int select(vector<int> &vec, int begin, int end, int i)
    {
    	if (begin == end&& begin != i)
    	{
    		cout << "return value is invalid" << endl;
    		return vec[begin];
    	}
    	vector<int> equalVec = partition(vec, begin, end);
    	if (i < equalVec[0])
    	{
    		return select(vec, begin, equalVec[0] - 1, i);
    	}
    	else if (i > equalVec[0])
    	{
    		return select(vec, equalVec[1] + 1, end, i);
    	}
    	else
    	{
    		return vec[i];
    	}
    }
    
    int findLastK1(const vector<int> &vec, int kTh)
    {
    	if (vec.size() == 0 || kTh > vec.size() || kTh < 1)
    	{
    		throw exception("I can't do it");
    	}
    	vector<int> myCopy(vec);
    	return select(myCopy, 0, myCopy.size() - 1, kTh - 1);
    }
    
    

    方法3

    vector<int> partitionbybfptr(vector<int> &vec, int left, int right, int targetValue)
    {
    	int more = right+1;
    	int less = left - 1;
    	while (left < more)
    	{
    		if (vec[left] < targetValue)
    		{
    			swap(vec[left++], vec[++less]);
    		}
    		else if (vec[left] > targetValue)
    		{
    			swap(vec[left], vec[--more]);
    		}
    		else
    		{
    			++left;
    		}
    	}
    	return vector<int>{less + 1, more-1};
    }
    
    void insertSort(vector<int> &vec, int beginIndex, int endIndex)
    {
    	if (endIndex-beginIndex < 1)
    	{
    		return;
    	}
    	for (int i = beginIndex+1; i < endIndex+1; ++i)
    	{
    		for (int j = i - 1; j >= beginIndex; --j)
    		{
    			if (vec[j] > vec[j + 1]) // 保证稳定性
    			{
    				swap(vec[j], vec[j + 1]);
    			}
    		}
    	}
    }
    
    int getMid(vector<int> &vec, int beginIndex, int endIndex)
    {
    	insertSort(vec, beginIndex, endIndex);
    	int sum = endIndex + beginIndex;
    	int mid = (sum / 2) + (sum % 2);
    	return vec[mid];
    }
    
    int selectbybfptr(vector<int> &vec, int begin, int end, int i);
    
    int medianOfMedians(vector<int> &vec, int begin, int end)
    {
    	int num = end - begin + 1;
    	int offset = num % 5 == 0 ? 0 : 1;
    	vector<int> midArr;
    	midArr.resize(num/5+offset);
    	for (int i = 0; i < num / 5 + offset;i++)
    	{
    		int beginI = begin + i*5;
    		int endI = beginI + 4;
    		midArr[i] = getMid(vec, beginI, min(endI,end));
    	}
    	return selectbybfptr(midArr, 0, midArr.size() - 1, midArr.size() / 2);
    }
    
    int selectbybfptr(vector<int> &vec, int begin, int end, int i)
    {
    	if (begin == end)
    	{
    		return vec[begin];
    	}
    	
    	int targetValue = medianOfMedians(vec,begin,end);
    	vector<int> equalVec = partitionbybfptr(vec, begin, end, targetValue);
    	if (i < equalVec[0])
    	{
    		return selectbybfptr(vec, begin, equalVec[0] - 1, i);
    	}
    	else if (i > equalVec[1])
    	{
    		return selectbybfptr(vec, equalVec[1] + 1, end, i);
    	}
    	else
    	{
    		return vec[i];
    	}
    }
    // BFPTR
    int findLastK2(const vector<int> &vec, int kTh)
    {
    	if (vec.size() == 0 || kTh > vec.size() || kTh < 1)
    	{
    		throw exception("I can't do it");
    	}
    	vector<int> myCopy(vec);
    	return selectbybfptr(myCopy, 0, myCopy.size() - 1, kTh - 1);
    }
    
    
    展开全文
  • 而目前解决 TOP-K 问题最有效的算法即是 BFPRT 算法,又称为中位数的中位数算法,该算法由 Blum、Floyd、Pratt、Rivest、Tarjan 提出,最坏时间复杂度为 $O(n)$。在首次接触 TOP-K 问题时,我们的第一反应就是可以先...

    一:背景介绍

    在一堆数中求其前 k 大或前 k 小的问题,简称 TOP-K 问题。而目前解决 TOP-K 问题最有效的算法即是 BFPRT 算法,又称为中位数的中位数算法,该算法由 Blum、Floyd、Pratt、Rivest、Tarjan 提出,最坏时间复杂度为 $O(n)$。

    在首次接触 TOP-K 问题时,我们的第一反应就是可以先对所有数据进行一次排序,然后取其前 k 即可,但是这么做有两个问题:

    快速排序的平均复杂度为 $O(nlogn)$,但最坏时间复杂度为 $O(n^2)$,不能始终保证较好的复杂度;

    我们只需要前 k 大的,而对其余不需要的数也进行了排序,浪费了大量排序时间。

    除这种方法之外,堆排序也是一个比较好的选择,可以维护一个大小为 k 的堆,时间复杂度为 $O(nlogk)$。

    那是否还存在更有效的方法呢?我们来看下 BFPRT 算法的做法。

    在快速排序的基础上,首先通过判断主元位置与k的大小使递归的规模变小,其次通过修改快速排序中主元的选取方法来降低快速排序在最坏情况下的时间复杂度。

    下面先来简单回顾下快速排序的过程,以升序为例:

    选取主元;

    以选取的主元为分界点,把小于主元的放在左边,大于主元的放在右边;

    分别对左边和右边进行递归,重复上述过程。

    二:算法过程及代码

    BFPRT 算法步骤如下:

    选取主元;

    1.1. 将 n 个元素按顺序分为 $⌊\frac n5⌋$ 个组,每组 5 个元素,若有剩余,舍去;

    1.2. 对于这 $⌊\frac n5⌋$ 个组中的每一组使用插入排序找到它们各自的中位数;

    1.3. 对于 1.2 中找到的所有中位数,调用 BFPRT 算法求出它们的中位数,作为主元;

    以 1.3 选取的主元为分界点,把小于主元的放在左边,大于主元的放在右边;

    判断主元的位置与 k 的大小,有选择的对左边或右边递归。

    上面的描述可能并不易理解,先看下面这幅图:

    1460000021363504

    BFPRT() 调用 GetPivotIndex() 和 Partition() 来求解第 k 小,在这过程中,GetPivotIndex() 也调用了 BFPRT(),即 GetPivotIndex() 和 BFPRT() 为互递归的关系。

    下面为代码实现,其所求为前 k 小的数:

    #include

    #include

    using namespace std;

    int InsertSort(int array[], int left, int right);

    int GetPivotIndex(int array[], int left, int right);

    int Partition(int array[], int left, int right, int pivot_index);

    int BFPRT(int array[], int left, int right, int k);

    int main()

    {

    int k = 8; // 1 <= k <= array.size

    int array[20] = { 11,9,10,1,13,8,15,0,16,2,17,5,14,3,6,18,12,7,19,4 };

    cout << "原数组:";

    for (int i = 0; i < 20; i++)

    cout << array[i] << " ";

    cout << endl;

    // 因为是以 k 为划分,所以还可以求出第 k 小值

    cout << "第 " << k << " 小值为:" << array[BFPRT(array, 0, 19, k)] << endl;

    cout << "变换后的数组:";

    for (int i = 0; i < 20; i++)

    cout << array[i] << " ";

    cout << endl;

    return 0;

    }

    /**

    * 对数组 array[left, right] 进行插入排序,并返回 [left, right]

    * 的中位数。

    */

    int InsertSort(int array[], int left, int right)

    {

    int temp;

    int j;

    for (int i = left + 1; i <= right; i++)

    {

    temp = array[i];

    j = i - 1;

    while (j >= left && array[j] > temp)

    {

    array[j + 1] = array[j];

    j--;

    }

    array[j + 1] = temp;

    }

    return ((right - left) >> 1) + left;

    }

    /**

    * 数组 array[left, right] 每五个元素作为一组,并计算每组的中位数,

    * 最后返回这些中位数的中位数下标(即主元下标)。

    *

    * @attention 末尾返回语句最后一个参数多加一个 1 的作用其实就是向上取整的意思,

    * 这样可以始终保持 k 大于 0。

    */

    int GetPivotIndex(int array[], int left, int right)

    {

    if (right - left < 5)

    return InsertSort(array, left, right);

    int sub_right = left - 1;

    // 每五个作为一组,求出中位数,并把这些中位数全部依次移动到数组左边

    for (int i = left; i + 4 <= right; i += 5)

    {

    int index = InsertSort(array, i, i + 4);

    swap(array[++sub_right], array[index]);

    }

    // 利用 BFPRT 得到这些中位数的中位数下标(即主元下标)

    return BFPRT(array, left, sub_right, ((sub_right - left + 1) >> 1) + 1);

    }

    /**

    * 利用主元下标 pivot_index 进行对数组 array[left, right] 划分,并返回

    * 划分后的分界线下标。

    */

    int Partition(int array[], int left, int right, int pivot_index)

    {

    swap(array[pivot_index], array[right]); // 把主元放置于末尾

    int partition_index = left; // 跟踪划分的分界线

    for (int i = left; i < right; i++)

    {

    if (array[i] < array[right])

    {

    swap(array[partition_index++], array[i]); // 比主元小的都放在左侧

    }

    }

    swap(array[partition_index], array[right]); // 最后把主元换回来

    return partition_index;

    }

    /**

    * 返回数组 array[left, right] 的第 k 小数的下标

    */

    int BFPRT(int array[], int left, int right, int k)

    {

    int pivot_index = GetPivotIndex(array, left, right); // 得到中位数的中位数下标(即主元下标)

    int partition_index = Partition(array, left, right, pivot_index); // 进行划分,返回划分边界

    int num = partition_index - left + 1;

    if (num == k)

    return partition_index;

    else if (num > k)

    return BFPRT(array, left, partition_index - 1, k);

    else

    return BFPRT(array, partition_index + 1, right, k - num);

    }

    运行如下:

    原数组:11 9 10 1 13 8 15 0 16 2 17 5 14 3 6 18 12 7 19 4

    第 8 小值为:7

    变换后的数组:4 0 1 3 2 5 6 7 8 9 10 12 13 14 17 15 16 11 18 19

    三:时间复杂度分析

    BFPRT 算法在最坏情况下的时间复杂度是 $O(n)$,下面予以证明。令 $T(n)$ 为所求的时间复杂度,则有:

    $$

    T(n)≤T(\frac n 5)+T(\frac {7n}{10})+c⋅n\tag{c 为一个正常数}

    $$

    其中:

    $T(\frac n 5)$ 来自 GetPivotIndex(),n 个元素,5 个一组,共有 $⌊\frac n5⌋$ 个中位数;

    $T(\frac {7n}{10})$ 来自 BFPRT(),在 $⌊\frac n5⌋$ 个中位数中,主元 x 大于其中 $\frac 12⋅\frac n5=\frac n{10}$ 的中位数,而每个中位数在其本来的 5 个数的小组中又大于或等于其中的 3 个数,所以主元 x 至少大于所有数中的 $\frac n{10}⋅3=\frac {3n}{10}$ 个。即划分之后,任意一边的长度至少为 $\frac 3{10}$,在最坏情况下,每次选择都选到了 $\frac 7{10}$ 的那一部分。

    $c⋅n$ 来自其它操作,比如 InsertSort(),以及 GetPivotIndex() 和 Partition() 里所需的一些额外操作。

    设 $T(n)=t⋅n$,其中 t 为未知,它可以是一个正常数,也可以是一个关于 n 的函数,代入上式:

    $$

    \begin{align}

    t⋅n&≤\frac {t⋅n}5+\frac{7t⋅n}{10}+c⋅n \tag{两边消去 n}\\

    t&≤\frac t 5+\frac {7t}{10}+c \tag{再化简}\\

    t&≤10c \tag{c 为一个正常数}

    \end{align}

    $$

    其中 c 为一个正常数,故t也是一个正常数,即 $T(n)≤10c⋅n$,因此 $T(n)=O(n)$,至此证明结束。

    接下来我们再来探讨下 BFPRT 算法为何选 5 作为分组主元,而不是 2, 3, 7, 9 呢?

    首先排除偶数,对于偶数我们很难取舍其中位数,而奇数很容易。再者对于 3 而言,会有 $T(n)≤T(\frac n 3)+T(\frac {2n}3)+c⋅n$,它本身还是操作了 n 个元素,与以 5 为主元的 $\frac {9n}{10}$ 相比,其复杂度并没有减少。对于 7,9,... 而言,上式中的 10c,其整体都会增加,所以与 5 相比,5 更适合。

    四:参考文献

    展开全文
  • BFPRT算法详解

    千次阅读 2018-06-21 16:09:32
    而目前解决TOP-K问题最有效的算法即是BFPRT算法,其又称为中位数的中位数算法,该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出,最坏时间复杂度为O(n)。在首次接触TOP-K问题时,我们的第一反应就是可以先对所有...
  • bfprt算法解析

    千次阅读 多人点赞 2018-07-26 09:58:29
    首先讲一下bfprt算法是干嘛的? bfprt算法是用来求数组中第k小的元素的算法,bfprt算法可以在O(n)时间内求出答案。 算法思想: 对于求数组中第k小的元素的问题,我们已经有很好的常规算法了,这个算法在最好的...
  • 那时候,我还不知道这个算法叫BFPRT算法——现在知道了,还知道它又被称为中位数的中位数算法,它的最坏时间复杂度为O(n),它的思想是修改快速选择算法的主元选取方法,提高算法在最坏情况下的时间复杂度。...
  • 那时候,我还不知道这个算法叫BFPRT算法——现在知道了,还知道它又被称为中位数的中位数算法,它的最坏时间复杂度为O(n)O(n)O(n) ,它是由Blum、Floyd、Pratt、Rivest、Tarjan提出,它的思想是修改快速选择算法的...
  • BFPRT算法详细解析

    2020-12-26 09:27:30
    BFPRT算法即是选取中位数的中位数的方式,找出数组n个元素中第k大的数。我们可以根据快速排序得到该值,但是快速排序的平均复杂度为O(nlog(n)),最坏时间复杂度为O(n^2)。而堆排序也是一个较好的方法,维护一个大小为...
  • BFPRT算法(TOP-K问题)

    2018-08-25 10:15:38
    而目前解决TOP-K问题最有效的算法即是BFPRT算法,其又称为中位数的中位数算法,该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出,最坏时间复杂度为O(n) 。 在首次接触TOP-K问题时,我们的第一反应就是可以先对...
  • 目录问题分析快排应用BFPRT算法 问题分析 面对这个问题,最简单的想法是对数据进行排序,然后根据下标即可找到第k小的元素,目前已知的排序算法的最低时间复杂度为O(nlog⁡2log⁡2n)O(n\sqrt{\log_2 {\log_2 n}})O...
  • 而目前解决TOP-K问题最有效的算法即是BFPRT算法,其又称为中位数的中位数算法,该算法由Blum、Floyd、Pratt、Rivest、Tarjan提出,最坏时间复杂度为O(n)。 二、算法实现 BFPRT算法步骤如下: (1):选取主元; ...
  • BFPRT(线性查找算法)

    万次阅读 2021-02-17 12:11:45
    BFPRT算法解决的问题十分经典,即从某n个元素的序列中选出第k大(第k小)的元素,通过巧妙的分析,BFPRT可以保证在最坏情况下仍为线性时间复杂度。该算法的思想与快速排序思想相似,当然,为使得算法在最坏情况下,...
  • 第K小的数BFPRT算法

    2021-01-30 15:23:30
    BFPRT是解决求一个数组中第K小的数的算法,可以时间O(N)的时间复杂度,而使用排序求第K小的数的算法的时间复杂度为O(NlogN),因此BFPRT算法更加高效 思想 (1)分组:将原数组每五个数分为一组,不足5个数的单分一组...
  • BFPRT详解

    2018-10-31 10:13:13
    由于保证了轴心数的品质,所以BFPRT算法的时间复杂度是严格的O(n)。 轴心数的选取: 分组:把partition的区域,每5个分成一组,最后不满5个的单独成一组 组内排序:每组数进行排序。 组成中位数数...
  • 问题分析 面对这个问题,最简单的想法是对数据进行排序,然后根据下标即可...O(n2)O(n^2) O(n2) BFPRT算法 不想写了,困了 重写了篇博客,内容和这一样,转到那边去吧:找到第k小的元素【top-k】:快排应用与BFPRT算法
  • 文章目录1 KMP算法1.1 KMP算法分析1.2 KMP算法应用题目1:旋转词题目2:子树问题2 bfprt算法2.1 bfprt算法分析2.2 bfprt算法应用 1 KMP算法 大厂劝退,面试高频^_^ 1.1 KMP算法分析 查找字符串问题:例如我们有一个...
  • 文章目录BFPRT算法的主要步骤和代码实现解决的问题解决方案BFPRT算法的步骤BFPRT算法的时间复杂度分析BFPRT算法的代码实现 BFPRT算法的主要步骤和代码实现 解决的问题 求一个无序数组中第k小的数。约定:k是从1开始...
  • BFPRT实现

    2017-07-22 16:52:33
    这里自己实现了一下BFPRT算法,并与别人的实现版本进行效率对比,以及与C++标准库中的sort排序后选取top-k进行效率对比。发现,C语言版本的效率更高一些,在数据量不是海量数据时,sort的速度竟然比BFPRT要快。 // /...
  • bfprt算法原理和复杂度估算

    千次阅读 2017-08-01 10:08:30
    bfprt算法的划分策略是:1、将数组每五个划为一组,不够5个单列一组 复杂度O(1)  2、每个组中的数据进行组内排序  复杂度O(n)  3、把每个组中的中位数拿出,组成一个新的数组 n/5 复杂度O(n)  4、...
  • 荷兰旗问题及随机快排和bfprt算法

    多人点赞 热门讨论 2022-01-11 20:31:13
     bfprt算法 BFPRT这一名称来源于该算法的五位作者的首字母,在维基百科上,该算法被称为Median of medians,因为中位数在这里起到了至关重要的角色。 在快速选择算法中,我们分析了最佳和最坏情况的时间复杂度。...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 1,323
精华内容 529
关键字:

BFPRT