CLRS - Lower bounds for sorting
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)
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)