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大牛 ^_^)
          主站蜘蛛池模板: 齐齐哈尔市| 莱阳市| 泸溪县| 巴彦淖尔市| 安岳县| 福安市| 莫力| 宝清县| 新宁县| 南宫市| 商河县| 黔江区| 习水县| 钟山县| 敦煌市| 阿合奇县| 新竹市| 台南县| 延长县| 宜章县| 博爱县| 苏尼特右旗| 常州市| 澄城县| 湖南省| 山西省| 得荣县| 永康市| 达日县| 黄山市| 荔波县| 山西省| 宝丰县| 崇州市| 阿合奇县| 根河市| 丽水市| 樟树市| 河源市| 普宁市| 宁陵县|