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

          CLRS - Lower bounds for sorting

          Posted on 2007-09-02 22:22 ZelluX 閱讀(336) 評(píng)論(0)  編輯  收藏 所屬分類: Algorithm
          搬到張江了

          1. 比較排序法最差情況下至少需要omega(n lgn)
          證明:
          通過(guò)決策樹(shù)(decision tree)分析比較排序,n!種可能情況都要被該決策樹(shù)的葉子覆蓋。
          設(shè)樹(shù)深度為h,有
          n! <= l <= 2h
          得h >= lg(n!) = omega(n lgn)

          2. 計(jì)數(shù)排序
          很簡(jiǎn)單的排序算法,不過(guò)后面的C數(shù)組的運(yùn)用比較技巧。
          for i = 1 to k
              do c[i] = 0
          for j = 1 to length(a)
              do c[a[j]] = c[a[j]] + 1
          // c 數(shù)組記錄了各個(gè)元素的出現(xiàn)次數(shù)
          for i = 1 to k
              do c[i] = c[i] + c[i - 1]
          // c[i] 記錄了小于或等于i的元素個(gè)數(shù)
          for j = length(a) downto 1
              do b[c[a[j]]] = a[j]
                  c[a[j]] = c[a[j]] - 1
          復(fù)雜度: k = O(n)時(shí),復(fù)雜度為theta(n)
          主站蜘蛛池模板: 松江区| 潞西市| 河池市| 大冶市| 威海市| 滨州市| 雷波县| 自治县| 新沂市| 东城区| 金寨县| 凤翔县| 抚顺县| 巫溪县| 永宁县| 朔州市| 会东县| 哈巴河县| 桑植县| 大埔区| 微山县| 盘山县| 寿阳县| 航空| 清徐县| 延庆县| 喀什市| 额敏县| 景东| 台北县| 固阳县| 镇原县| 施甸县| 万山特区| 襄城县| 宁国市| 叶城县| 阜阳市| 望都县| 莱西市| 江口县|