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)
          主站蜘蛛池模板: 乌苏市| 安岳县| 大石桥市| 金川县| 思南县| 沂水县| 金坛市| 苍溪县| 策勒县| 滦平县| 蕲春县| 伊通| 布尔津县| 顺昌县| 基隆市| 马鞍山市| 抚州市| 永泰县| 武穴市| 哈尔滨市| 德州市| 右玉县| 黑龙江省| 山丹县| 沅江市| 根河市| 乐都县| 武定县| 百色市| 长汀县| 久治县| 南安市| 安龙县| 凤阳县| 册亨县| 镇康县| 陵川县| 东光县| 涿鹿县| 隆尧县| 微山县|