Unit1_1：分治问题之时间复杂度求解

背景

当碰到形如$T(n)=aT(\lceil \frac{n}{b}\rceil )+O(n^d)$的递推式，本质上就是将问题转化为规模更小的子问题求解，此时有三种思路。

递归树法

案例一

$T(n)=\{\begin{array}{ll}2T(\frac{n}{2})+n& ifn>1\\ 1& ifn=1\end{array}$
可以利用递归树：

画出树，高满足$2^h=n$，因此$h=lo{g}_{2}n$，而叶子共有n个，因此总的时间复杂度$T(n)=nlogn$

案例二

$T(n)=\{\begin{array}{ll}3T(\frac{n}{4})+n^2& ifn>1\\ 1& ifn=1\end{array}$

每层个数即$3^h$个。最后一层高度$h=lo{g}_{4}n$，再利用对数技巧代入，即可求出叶子的个数，而时间复杂度为：

等比数列求解

局限性

$T(n)=\{\begin{array}{ll}T(\frac{n}{3})+T(\frac{2n}{3})+n& ifn>2\\ 1& ifn=1,2\end{array}$

此时树的高度不一致，无法计算

代入法/替代法

此法先假设时间复杂度，再去验证假设成立。因此最难之处在于怎么假设，用处不大

主方法（重点）

$T(n)=aT(\lceil \frac{n}{b}\rceil )+O(n^d)$的时间复杂度如下：

$T(n)=\{\begin{array}{ll}O(n^d)& d>{\log }_{b}a\\ & \\ O(n^{d}logn)& d={\log }_{b}a\\ & \\ O(n^{{\log }_{b}a})& d<{\log }_{b}a\end{array}$

以后碰到这种递推分治式子代入公式即可