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

          O(n)時間求出最小的k個數

          Posted on 2007-09-04 18:55 ZelluX 閱讀(485) 評論(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在選數時做了一個優(yōu)化,這樣在最差情況下也有O(n)的復雜度了,實際應用中沒什么用 (thx to Peter大牛 ^_^)
          主站蜘蛛池模板: 青川县| 疏附县| 乌海市| 资溪县| 松溪县| 临潭县| 揭阳市| 民乐县| 盱眙县| 鄄城县| 蕉岭县| 娄底市| 合川市| 新蔡县| 双江| 西乡县| 托里县| 荔浦县| 淅川县| 德江县| 甘德县| 湘乡市| 永丰县| 花莲县| 前郭尔| 东平县| 邯郸市| 泾川县| 崇明县| 綦江县| 靖宇县| 垫江县| 同仁县| 南安市| 始兴县| 大竹县| 会泽县| 天水市| 井陉县| 霍邱县| 禹州市|