Steven_Meng's Blog

引理

$\sum _{i=0} ^ {\log_2n} 2^i =n$（注意这里的等于只是量级上面的等于）

画长方形法

例题1

归并排序时间复杂度$T(n)=2T(\frac{n}{2})+O(n)$

可以画图分析，显然每层都是$n$，有$\log n$层，所以是$O(n\log n)$

例题2

$T(n)=4T(\frac{n}{2}) + n$

可以看出只有$\log n$层，但是每层相比于上层都乘了$2$。

总共$n\sum _{i=0}^{\log n} 2^i = n^2$