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)