Steven_MengのBlog

引理

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

画长方形法

例题1

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

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

例题2

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

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

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

 评论