CLRS笔记2：算法入门

1，增量法(incremental)
例：插入排序(insertion sort)
ruby版本：

def insertion_sort(a)
  a.each_with_index do |el,i|
    j = i - 1
    while j >= 0
      break if a[j] <= el
      a[j + 1] = a[j]
      j -= 1
    end
    a[j + 1] = el
  end
end

erlang版本：

-module(insertion_sort).
-export([sort/1]).

sort(List) ->
  sort(List, []).

sort([H | T], Acc) ->
  sort(T, insert(H, Acc));

sort([], Acc) ->
  Acc.

insert(E, Acc = [H | _T]) when E < H ->
  [E | Acc];

insert(E, [H | T]) when E >= H ->
  [H | insert(E, T)];

insert(E, []) ->
  [E].

循环了1+2+3+...+(n-1) = n(n+1)/2次，时间为Θ(n^2)

2，分治法(divide-and-conquer)
例：合并排序(merge sort)
ruby版本：

def merge(l, r)
  result = []
  while l.size > 0 and r.size > 0 do
    if l.first < r.first
      result << l.shift
    else
      result << r.shift
    end
  end
  if l.size > 0
    result += l
  end
  if r.size > 0
    result += r
  end
  result
end

def merge_sort(a)
  return a if a.size <= 1
  middle = a.size / 2
  left = merge_sort(a[0, middle])
  right = merge_sort(a[middle, a.size - middle])
  merge(left, right)
end

erlang版本：

-module(merge_sort).
-export([sort/1]).

sort([]) -> [];
sort([L]) -> [L];
sort(List) ->
    {Left, Right} = lists:split(length(List) div 2, List),
    merge(sort(Left),sort(Right)).
merge(L, []) -> L;
merge([], R) -> R;
merge([L|Left], [R|_]=Right) when L < R ->
    [L | merge(Left, Right)];
merge(Left, [R|Right]) ->
    [R | merge(Left, Right)].

运行了n/2+n/4+n/8+... = n次，时间为Θ(n)


回家又看了一下merge sort的时间复杂度的计算方法，发现自己想错了:
merge时间并不是n/2 n/4 n/8的数列
一个数组一直切分切分，最后如果切分到size = 1时，可以认为merge时间为n/2，但向上归并时size > 1时，这时的merge时间不是简单的上级的1/2

正确的公式T(n) = 2T(n/2) + cn，其中cn表示合并两个子数组的时间，为n的线性函数，分解时间为Θ(1)，可以忽略
算法导论对merge sort的时间复杂度的推算方法是扩展递归树：
T(n)
||
cn + T(n/2) + T(n/2)
||
cn + (cn/2 + cn/2) + T(n/4) + T(n/4) + T(n/4) + T(n/4)
||
...
cn + (cn/2 + cn/2) + (cn/4 + cn/4 + cn/4 + cn/4) + .... + (c + c + c + ...)
||
cn + (cn/2 + cn/2) + (cn/4 + cn/4 + cn/4 + cn/4) + .... + (cn*(1/2)^x + cn*(1/2)^x + cn*(1/2)^x + ...)

cn*(1/2)^x = c
x = lgn

即一共有lgn + 1层，而每层加起来的和又是cn，所以T(n) = cn*(lgn + 1) = Θ(nlgn)

评论

1 楼 blackanger 2008-10-23  

来学习学习，这个系列不错