posts - 403, comments - 310, trackbacks - 0, articles - 7
            BlogJava :: 首頁 :: 新隨筆 :: 聯(lián)系 :: 聚合  :: 管理

          O(n)時(shí)間求出最小的k個(gè)數(shù)

          Posted on 2007-09-04 18:55 ZelluX 閱讀(485) 評論(0)  編輯  收藏 所屬分類: Algorithm
          一種做法是用最差情況下復(fù)雜度也是O(n)的算法求出第k大的數(shù),然后把這個(gè)數(shù)作為pivot進(jìn)行一次paritition,再排序該數(shù)左邊的部分。復(fù)雜度為O(n + klgk)

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

          另外,CLRS上Selection in worst-case linear time算法實(shí)際上對in expected linear time在選數(shù)時(shí)做了一個(gè)優(yōu)化,這樣在最差情況下也有O(n)的復(fù)雜度了,實(shí)際應(yīng)用中沒什么用 (thx to Peter大牛 ^_^)
          主站蜘蛛池模板: 桐庐县| 周至县| 镇康县| 汉中市| 安义县| 嘉善县| 石楼县| 称多县| 南投县| 宁阳县| 体育| 马公市| 衡南县| 嘉祥县| 雅江县| 维西| 西丰县| 辽宁省| 东乌珠穆沁旗| 金山区| 康平县| 宣化县| 英吉沙县| 阿拉善右旗| 永定县| 保德县| 加查县| 武功县| 禹城市| 古交市| 昭平县| 磐安县| 大丰市| 宜良县| 齐齐哈尔市| 紫云| 谷城县| 清河县| 明光市| 北碚区| 瑞丽市|