## 分治问题中递归函数时间复杂度浅析

### 代入法(The substitution method)

_e.g._ 求$T(n) = 2T(\lfloor \frac{n}{2} \rfloor) + n$的时间复杂度上界(upper bound).

### 主定理法(The master method)

$a,b$均为大于等于$1$的常数，$f(n)$是一个渐进正函数(asymptotically positive function)

1. If $f(n)=O(n^{\log_ba-\epsilon})$ for some constant $\epsilon>0$,then $T(n)=\Theta(n^{\log_ba})$.

2. If $f(n)=\Theta(n^{\log_ba})$,then $T(n)=\Theta(n^{\log_ba}\lg n)$.

3. If $f(n)=\Omega(n^{\log_ba+\epsilon})$ for some constant $\epsilon>0$, and if $af(n/b)\le cf(n)$ for some constant $c<1$ and all sufficiently large $n$,then $T(n)=\Theta(f(n))$.

Introduction To Algorithms,Page 94, 3rd edition

#### 递归建堆 $T(n) = T(2n/3) + 1$

$a=1, b=\frac{3}{2}, log_b^a = 0, n^{log_b^a} = 1 = f(n)$

#### 归并排序 $T(n)=2T(n/2)+ \Theta(n)$

$a=2, b=2, n^{log_b^a} = n$

### References

Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to algorithms. MIT press., http://thuvien.thanglong.edu.vn:8081/dspace/bitstream/DHTL_123456789/3760/2/introduction-to-algorithms-3rd-edition.pdf