Posted on 2007-09-02 22:22
ZelluX 閱讀(332)
評論(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)