找最小的K个数 – Stay hungry, Sta y foolish – 博客频道 – CSDN.NET

From Evernote:

找最小的K个数 – Stay hungry, Stay foolish – 博客频道 – CSDN.NET

Clipped from: http://blog.csdn.net/huagong_adu/article/details/6901924

找最小的K个数 – Stay hungry, Stay foolish – 博客频道 – CSDN.NET

SourceURL: http://blog.csdn.net/huagong_adu/article/details/6901924

您还未登录!|登录|注册|帮助

Stay hungry, Stay foolish

4月18日22:00至4月19日2:00网站服务暂停公告 博客频道4月技术图书有奖试读火爆开启 移动业界领袖会议·上海·6.20
CSDN十大风云博客专栏评选结果公布! 下载频道分享季1:分享经典,领取积分! CSDN博客皮肤评选活动火爆开启!

找最小的K个数

分类: 算法 2011-10-24 23:51 572人阅读 评论(3) 收藏 举报

今天在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

分享到:

顶3踩0

查看评论
2楼 qiul12345 2011-11-30 19:56发表 [回复] [引用] [举报]恩恩。很不错啊,经典的问题。哈1楼 v_JULY_v 2011-10-25 12:24发表 [回复] [引用] [举报]文章总结的很好。但文中第5点建立最小堆的思路,事实上,逊于建立最大堆找最小的k个数的思路。你没有注意到原文中有这样一句话:“但,最重要的是,如果建立n个元素的最小堆的话,那么其空间复杂度势必为O(N),而建立k个元素的最大堆的空间复杂度为O(k)。所以,综合考虑,我们一般还是选择用建立k个元素的最大堆的方法解决此类寻找最小的k个数的问题。”Re: huagong_adu 2011-10-25 14:03发表 [回复] [引用] [举报]回复v_JULY_v:我只考虑了时间复杂度,疏忽了。还要看n的大小,当n很大的时候用最大堆的方法确实在空间上有优势。综合时空两个方面来说还是最大堆比较有优势。谢谢提醒!
您还没有登录,请[登录][注册]

* 以上用户言论只代表其个人观点,不代表CSDN网站的观点或立场

  • 个人资料

  • huagong_adu

    • 访问:14941次
    • 积分:476分
    • 排名:第16586名
    • 原创:18篇
    • 转载:14篇
    • 译文:0篇
    • 评论:55条
  • 我的新浪微博
  • 我的关注
  • Famous blog
  • 文章分类
  • 阅读排行
  • 评论排行
  • 最新评论
  • 文章存档
  • 文章搜索

问题报告北京创新乐知信息技术有限公司 版权所有, 京 ICP 证 070598 号世纪乐知(北京)网络技术有限公司 提供技术支持江苏乐知网络技术有限公司 提供商务支持 Email:webmaster

找最小的K个数 – Stay hungry, Stay foolish – 博客频道 – CSDN.NET

SourceURL: http://blog.csdn.net/huagong_adu/article/details/6901924
Author: weixin <cbweixin@hotmail.com>

http://blog.csdn.net/huagong_adu/article/details/6901924

This entry was posted in Uncategorized. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s