今天在CSDN无意中看到July一篇号称《当今世界最为经典的十大算法》的博文,感觉这文章名字挺霸气,于是进去瞅了一眼。看到其中有一个叫做BFPRT的算法,据说可以最坏情况下也能以O(N)复杂度找到数组中的第K大元素。博文里有链接到详细解释这个算法的另外一篇博文,于是又点进去,准备看看这算法是如何神奇,居然可以如此高效!
文章是以这样一个问题开始的:如何在一堆数据中找出最小的K个数。
随便想了一下,想了几种方法:
1. 先对数据排序,然后取出前K个数。排序算法很多,什么插入排序、快速排序等等,不过都不可能最坏也能到达O(N);
2. 开一个 |K| 大小的数组,先从这堆数据中装入前K个数,找出这K个数中的最大数Max(K),然后从第K+1个数开始向后找,如果有小于这个Max(K)的,则替换掉这个数,然后从这K个数中重新找出最大的Max(K)。这样一直向后扫描,得到结果。这个算法的复杂度最坏是O(Kn),也不行;
3. 堆,脑子里闪过这么个想法,只能算是灵感之类的东西,不过没细想。
因为急切想看看这个所谓的BFPRT算法到底是怎么回事,所以只是稍微思考了一下,没怎么细想。
博文也列出了几个可能解决这个问题的解法:
1. 跟我想的一样,排序,取数,最笨的方法,也是最容易想到的;
2. 也跟我想的一样,同上面的2(看来我还不是最笨的);
3. 比较笨的方法,扫描数据堆K遍,每遍找出最小的那个数,复杂度为O(Kn);
4. 果然用到堆(可惜我没细想)!想法跟2类似,先用数据中的前K个数建一个最大堆,建堆复杂度是O(K),然后从第K+1个数开始向后扫描,遇到小于堆顶元素时替换掉堆顶元素,更新堆,这个操作的复杂度是O(logK)。所以总的时间是O(K+(n-K)*logK)=O(n*logK),比方法2的O(nK)稍微好一点。
这种方法有个好处,就是当数据量很大时,如果内存放不下所有的数据,用这方法可以解决这个问题。先读出一部分数据,建堆,处理完这部分数据,再读出一部分数据,如此循环下去,直达数据处理完为止。
5. 也是用堆,不过是对整个数据建一个最小堆(O(n)),然后取出堆顶元素,每取完一次更新一次堆(O(logn)),取K次,所以总的复杂度是O(n+K*logn);
可以证明O(n+K*logn) < O(n*logK),即建立n个元素是最小堆然后取前K个堆顶元素的方法比建立一个K个元素的最大堆然后比较所有数据得到最小的K个数的方法在时间复杂度上稍微优越一点,但两者实际上是一个数量级,在那篇博文里面,作者特意写了实现了这两种方法去处理一组大数据,结果表明两种方法的时间实际上相差不多。
但在空间上,最大堆只需要O(K)的空间复杂度,而最小堆需要O(n),所以综合来讲,最大堆解决这种方法比最小堆有优势。
算法改进:每次取走堆顶元素更新堆时,正常是把堆中最后一个元素放到堆顶(暂且称为 !Top),然后调整堆把!Top下调到他应该在的位置。改进后,!Top不用下调到他原所应该在的位置,而是下调顶多K次就可以了。具体如下:
建立n的最小堆之后,取走堆顶元素(第一个数),然后将最后的数!Top调到堆顶,把!Top下调至多K-1层形成新的堆;接着取走堆顶元素(第二个数),同样,更新堆的时候!Top下调至多K-2层...直到取走第K个数时,不再更新堆(此时的堆已经不是最小堆),算法结束,已经取得最小的K个数,最后的“堆”是不是堆已经跟我没关系了。
改进后的复杂度:建堆O(n),更新堆O(K),K次更新为O(K*K)=O(K^2),所以总的复杂度是O(n+K^2),比改进前的O(n+K*logn)要好。
6. 用快速排序的思想,先选取一个数作为基准比较数(作者称为“枢纽元”,即pivot),用快排方法把数据分为两部分Sa和Sb。
如果K< |Sa|(|Sa|表示Sa的大小),则对Sa部分用同样的方法继续操作;
如果K=|Sa|,则Sa是所求的数;
如果K=|Sa| + 1,则Sa和这个pivot一起构成所求解;
如果K>|Sa| +1,则对Sb部分用同样的方法查找最小的(K-|Sa|-1)个数(其中Sa和pivot已经是解的一部分了)。
与快排不同,快排每次都要对划分后的两部分数据都继续进行同样的快排操作,快速选择(暂时这么称呼这种算法吧)不同,只对其中一部分进行操作即可。
BFPRT算法就是在这个方法的基础上进行改进的。BFPRT算法主要改进是在选取pivot上面,一般快排是在数据堆取第一个或最后一个数最为pivot,而BFPRT算法采用“五分化中位数的中位数”方法取得这个pivot,从而使算法复杂度降低到O(N),具体方法如下:
以5个数为一组对数据进行划分,最后一组数据的个数为n%5,然后对每组数据用插入排序方法选出中位数,对选出的中位数用同样的方法继续选,最后选出这些数的中位数作为pivot,即可达到O(N)的效率。
算法的具体证明我没仔细看。那篇博文实在太长,估计是续写了好多次,修改了n遍,感觉组织有点乱,看到头有点晕,再找时间仔细看这算法的证明。具体可以参考:
Mark Allen Weiss的数据结构与算法分析--c语言描述,第10章,第10.2.3节
算法导论,第9.2、9.3节
编程之美第一版,第141页,第2.5节 寻找最大的k个数
M. Blum, R.W. Floyd, V. Pratt, R. Rivest and R. Tarjan, "Time bounds for selection"
编程珠玑II 第15章第15.2节程序
总结:如果当时细想的话说不定也能多想几个方法;有了解法之后,多想想这样的算法是不是已经最优,还能不能再优化,比如一开始用排序,排序需要浪费时间,是不是可以不用排序的方法,不用排序方法里面可能想到堆,堆是不是每次都必须调整到“完全正确的堆”,也可能用快排,快排是不是每次都排两部分划分的数据,等等;多想想把学过的数据结构灵活应用,比如这里面用到的堆和快排,以前是用于数据排序,现在用来数据选择,blahblah...总结完毕。
本文参考:《程序员编程艺术:第三章、寻找最小的k个数》http://blog.csdn.net/v_JULY_v/article/details/6370650
分享到:
相关推荐
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 这个题目完成的思路有很多,很多排序算法都可以完成既定操作,关键是复杂度性的考虑。以下几种思路当是笔者...
对于给定的n位正整数a 和正整数k,设计一个算法找出剩下数字组成的新数 最小的删数方案。 «编程任务: 对于给定的正整数a,编程计算删去k个数字后得到的最小数。 Input 由文件input.txt提供输入数据。文件的第1...
输入n个整数,找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字,则最小的4个数字是1,2,3,4,。 解法1 使用partition函数可以知道,使用==O(N)==的时间复杂度就可以找出第K大的数字,并且左边的数字比这个数小...
试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。 输入格式 可输入多组测试数据(不超过50组测试数据),每组测试数据分两行,每行一个数,数的含义如下。 第一行:正整数a(a是大于0的一个n...
使相邻顶点着有不同颜色的最小着色数,相应于要找的最小会场数。) 编程任务: 对于给定的k个待安排的活动,编程计算使用最少会场的时间表。 Input 输入数据是由多组测试数据组成。每组测试数据输入的第一行有1 个...
设计算法实现在一个具有在n各互不相同元素的数组A[1…n]中找出所有前k个最小元素的问题,这里k不是常量,即它是输入数据的一部分。要求算法的时间复杂性为Θ(n)。 2. 具体要求 输入的第一行是一个正整数m,表示测试...
用C语言利用数组来模拟实现一个堆的结构
问题描述: 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1)位的正整数a和k,...试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。
问题描述: 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1)位的正整数a和k,...试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。
1. 设计程序利用分治策略求n个数的最大值和最小值。 2. 利用分治策略,在n个不同元素中找出第k个最小元素。
找出最大或最下的K个元素,可以使用Python库中的heapq模块,该模块提供两个函数nlargest()求最大K个和nsmallest()求最小K个。 下面我们举例说明: import heapq nums=[12,-9,-3,32,9,56,23,0,11,34] print(heapq....
问题描述: 给定n位正整数a,去掉其中任意k个数字后,剩下的数字按原次序排列成一个新的正整数。 算法设计: 给定n (1)位的正整数a和k,...试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。
找出乱序中最小k的位置(快速排序) 快速排序算法,时间复杂度o(nlogn),但是不稳定最坏的时候能达到O(n^2) 题目:找出乱序中最小k的位置 如何从N个乱序数据中,快速地找出第K小的数? 有数据 2,6,3,5,7,9,找出最小k...
使用由 C-MEX 实现的部分快速排序算法。 复杂度为 O(n + k.log(k)),其中 n 是数组的大小,k 是要选择的元素数。 对于大尺寸输入,比 SORT 或多次调用 MIN/MAX 快。 支持多维能力
试着设计一个算法,找出删去k个数,剩下数字组成的新数最小的删数方案。 Input 可输入多组测试数据(不超过50组测试数据),每组测试数据分两行,每行一个数,数的含义如下。 第一行:正整数a(a是大于0的一个n位正...
求有N个元素的数组中前k个最大的数?(N>=k) 方法一:排序法 可以先将数组排序,然后再截取...(1)维护一个大小为k的小顶堆(降序排列,堆顶元素最小),用来存储前k个最大的数,堆顶保存了堆中最小的数; (2)每次遍
TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词. 方法一: 先排序,然后截取前k个数. 时间复杂度:O(n*logn)+O(k)=O(n*logn)。 这种方式比较简单粗暴,提一下便是。 方法...