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大牛 ^_^)
          主站蜘蛛池模板: 大竹县| 松滋市| 大城县| 金湖县| 桃园市| 博客| 全椒县| 张北县| 霞浦县| 长寿区| 大石桥市| 两当县| 宜兰市| 河东区| 龙江县| 吉首市| 遂平县| 广汉市| 信宜市| 合山市| 罗山县| 南京市| 岳普湖县| 太保市| 揭东县| 迁安市| 阜康市| 洪江市| 宜都市| 长阳| 宁都县| 柯坪县| 阳西县| 靖州| 沂源县| 策勒县| 北宁市| 丹江口市| 阿勒泰市| 祁门县| 麻城市|