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

本文主要是介绍Unit1_1：分治问题之时间复杂度求解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

文章目录

背景
递归树法
- 案例一
- 案例二
- 局限性
代入法/替代法
主方法（重点）

背景

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

递归树法

案例一

$T(n)=\left\{ \begin{array}{ll} 2T(\frac{n}{2})+n & if \space n>1 \\ 1 & if \space n=1 \nonumber \end{array} \right.$
可以利用递归树：
在这里插入图片描述
画出树，高满足 $2^h=n$ ，因此 $h=log_{2}n$ ，而叶子共有n个，因此总的时间复杂度 $T (n) = n l o g n$

案例二

$T(n)=\left\{ \begin{array}{ll} 3T(\frac{n}{4})+n^2 & if \space n>1 \\ 1 & if \space n=1 \nonumber \end{array} \right.$
在这里插入图片描述
每层个数即 $3^h$ 个。最后一层高度 $h=log_4n$ ，再利用对数技巧代入，即可求出叶子的个数，而时间复杂度为：

等比数列求解

局限性

$T(n)=\left\{ \begin{array}{ll} T(\frac{n}{3})+ T(\frac{2n}{3})+n & if \space n>2 \\ 1 & if \space n=1,2 \nonumber \end{array} \right.$
在这里插入图片描述
此时树的高度不一致，无法计算

代入法/替代法

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

主方法（重点）

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

$T(n)=\left\{ \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 \nonumber \end{array} \right.$