遞迴的複雜度.md

二分搜尋法 log(n)

T(n) = T(n/2)+1
T(1) = 1

令 n = 2^k

T(2^{k})   = T(2^{k-1})+1
T(2^{k-1}) = T(2^{k-2})+1
...
T(2)       = T(1)      +1
--------------------------
左右消去得 T(2^{k}) = 1+1+...+1 (共 k 次) = k
          T(n)                          = log(n)

Merge Sort -- log(n)

T(n) = 2*T(n/2)+1
T(1) = 0

令 n = 2^k

            T(2^{k})   = 2*T(2^{k-1})+2^{k}
2*          T(2^{k-1}) = 2*T(2^{k-2})+2^{k-1}
2^2*        T(2^{k-1}) = 2*T(2^{k-2})+2^{k-2}
...
2^{k-1}*    T(2)       = 2*T(1)      +2^1
--------------------------
左右消去得 T(2^{k}) = 2^k (1+1) (共 k 次) = 2^{k+1} k
          T(n)                          = 2 n log(n)