Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

O(n)时间求出最小的k个数

Posted on 2007-09-04 18:55 ZelluX 阅读(385) 评论(0)  编辑  收藏 所属分类: Algorithm
一种做法是用最差情况下复杂度也是O(n)的算法求出第k大的数,然后把这个数作为pivot进行一次paritition,再排序该数左边的部分。复杂度为O(n + klgk)

http://en.wikipedia.org/wiki/Selection_algorithm

另外,CLRS上Selection in worst-case linear time算法实际上对in expected linear time在选数时做了一个优化,这样在最差情况下也有O(n)的复杂度了,实际应用中没什么用 (thx to Peter大牛 ^_^)

只有注册用户登录后才能发表评论。


网站导航: