Snowdream

I'm awake but my world is half asleep
posts - 403, comments - 310, trackbacks - 0, articles - 7
  BlogJava :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

CLRS - Lower bounds for sorting

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

只有注册用户登录后才能发表评论。


网站导航: