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

          CLRS - Lower bounds for sorting

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

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

          2. 計數排序
          很簡單的排序算法,不過后面的C數組的運用比較技巧。
          for i = 1 to k
              do c[i] = 0
          for j = 1 to length(a)
              do c[a[j]] = c[a[j]] + 1
          // c 數組記錄了各個元素的出現次數
          for i = 1 to k
              do c[i] = c[i] + c[i - 1]
          // c[i] 記錄了小于或等于i的元素個數
          for j = length(a) downto 1
              do b[c[a[j]]] = a[j]
                  c[a[j]] = c[a[j]] - 1
          復雜度: k = O(n)時,復雜度為theta(n)
          主站蜘蛛池模板: 澄江县| 丽水市| 鲁山县| 武汉市| 耒阳市| 宜阳县| 尼勒克县| 临湘市| 西城区| 海丰县| 新巴尔虎右旗| 都安| 视频| 巴楚县| 平遥县| 若尔盖县| 白朗县| 庄浪县| 仲巴县| 洛隆县| 行唐县| 高阳县| 德令哈市| 仁布县| 平阴县| 原平市| 奉节县| 黑龙江省| 巨鹿县| 东兰县| 南京市| 扎囊县| 沙湾县| 固镇县| 长白| 大同市| 遂溪县| 平罗县| 绿春县| 玛纳斯县| 敖汉旗|