`
nudtgk2000
  • 浏览: 71508 次
  • 性别: Icon_minigender_1
  • 来自: 大连
社区版块
存档分类
最新评论

选前K个最大数算法小洁

 
阅读更多

在N个元素中选取前K个最大数,流传较多的是利用小顶堆和利用快排中的partition两种方法:

http://www.kuqin.com/algorithm/20111105/314362.html

http://www.kuqin.com/algorithm/20111105/314363.html

前者的复杂度稳定在o(n*logk),而后者虽然平均复杂度也在o(n*logk), 但是单次复杂度依赖于划分点pivot的选择, 极端情况下会退化为o(n*k).

所以我觉得还是小顶堆比较好.

 

附:堆排序算法

 

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics