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

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

          Posted on 2007-09-04 18:55 ZelluX 閱讀(485) 評論(0)  編輯  收藏 所屬分類: Algorithm
          一種做法是用最差情況下復(fù)雜度也是O(n)的算法求出第k大的數(shù),然后把這個數(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í)做了一個優(yōu)化,這樣在最差情況下也有O(n)的復(fù)雜度了,實(shí)際應(yīng)用中沒什么用 (thx to Peter大牛 ^_^)
          主站蜘蛛池模板: 丰台区| 日土县| 郴州市| 五大连池市| 墨脱县| 香格里拉县| 黄平县| 南丰县| 沂水县| 同仁县| 四川省| 崇礼县| 平谷区| 保靖县| 吉林省| 白城市| 中牟县| 扎囊县| 沿河| 银川市| 三亚市| 纳雍县| 大足县| 柳江县| 鞍山市| 九台市| 安塞县| 黎川县| 永昌县| 桂平市| 饶河县| 三江| 类乌齐县| 安溪县| 达孜县| 瓦房店市| 泗水县| 长宁县| 和顺县| 余姚市| 新乡市|