Posted on 2007-09-02 22:22
ZelluX 阅读(326)
评论(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)