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)
          主站蜘蛛池模板: 陆川县| 双柏县| 太康县| 张家港市| 屏东市| 普定县| 祁连县| 永新县| 习水县| 千阳县| 肇州县| 长兴县| 开化县| 盖州市| 呼和浩特市| 寿光市| 化州市| 通河县| 通道| 梧州市| 运城市| 同德县| 井冈山市| 武安市| 郸城县| 麦盖提县| 分宜县| 蒲城县| 金山区| 阆中市| 定西市| 育儿| 涟水县| 年辖:市辖区| 韶关市| 安塞县| 太白县| 富宁县| 芦山县| 眉山市| 贵阳市|