递推法求阶乘时间复杂度

int fact(int n){
	if(n == 1)
		return 1;
	return n * fact(n - 1);
}

$T(n)=\begin{cases}1&n=1\\T(n-1)+1&n>1\end{cases}$

$\begin{aligned}T(n) & =T(n-1)+1 \\ & = T(n-2)+2\\ &= \dots \\ &= T(1)+n-1 \\ &= n \\ &= O(n)\end{aligned}$

主定理求递归时间复杂度

采用分治策略的代码，通常设计为递归算法来实现，其时间复杂性递归定义一般可写成如下形式。

$T(n)=\begin{cases}O(1)&n=n_0\\aT(\frac{n}{b})+f(n^d)&n>n_0\end{cases}$

$a≥1，b>1$为常数，$f(n)$是正函数。

T(n) 代表了当前层的时间复杂度，n 是问题规模大小。

$a$ 是原问题的子问题个数， $\frac{n}{b}$ 是每个子问题的大小，这里假设每个子问题有相同的规模大小。

$f(n^d )$ 代表了将当前层的数据进行分解和将返回当前层的数据进行合并所需要的时间复杂度。

根据主定理：设 a≥1，b>1 为常数，设 f(n) 是正函数，T(n) 由递归式 $T(n)=aT(\frac{n}{b})+f(n^d)$

T(n) 有如下渐进界：

$T(n)=\begin{cases}O(n^d)& d>log_ba\\O(n^dlogn)&d=log_ba \\ O(n^{log_ba}) & d<log_ba\end{cases}$

• 如果 $d>log_ba$，$∃ε>0$，有 $f(n^d)=O(n^{log_ba+ε})$，且对 $∀c<1$ 与所有足够大的 $n$，有 $af(\frac{n}{b})≤cf(n)$，则 $T(n)=O(n^d)$
• 如果 $d=log_ba$，则 $T(n)=O(n^dlogn)$
• 如果 $d<log_ba$，$∃ε>0$，有 $f(n^d)=O(n^{log_ba-ε})$，则 $T(n)=O(n^{log_ba})$

例1

棋盘覆盖问题时间复杂度

$T(n)=\begin{cases}1&n=1\\4T(\frac{n}{2})+1&n>1\end{cases}$

$a=4,b=2,d=0$

$n^{log_ba}=n^2$

$f(n)=1$

$\Rightarrow d<log_ba$ 则 $T(n)=O(n^{log_ba})=O(n^2)$

例2

归并排序时间复杂度

$T(n)=\begin{cases}1&n=1\\2T(\frac{n}{2})+n&n>1\end{cases}$

$a=2,b=2,d=1$

$d=log_ba$，则$T(n)=nlogn$

例3

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

$a=4,,b=2,d=3$

$d>log_ba$，此时 $ε=1$

$f(n)=O(n^3)$

$4f(\frac{n}{2})=4(\frac{n}{2})^3=\frac{n^3}{2}≤cf(n)$，$\frac{1}{2}≤c<1$

不能用主定理求解情况

$T(n)=\begin{cases}1&n=1\\2T(\frac{n}{2})+nlogn&n>1\end{cases}$

$n^{log_ba}=n,f(n)=nlogn$

$\Rightarrow d>log_ba$

但是由于找不到一个常数 $ε$，使得 $f(n)=O(n^{log_ba+ε})$，因此不适用主定理。

递归树求递归时间复杂度

对递归树所产生的所有项求和就是递归方程的解。

例1：

快速排序

$T(n)=\begin{cases}1&n=1\\2T(\frac{n}{2})+n&n>1\end{cases}$

层数共计：$k$ 层

$k=logn$

$T(n)=O(nlogn)$

例2：

棋盘覆盖

$T(n)=\begin{cases}1&n=1\\4T(\frac{n}{2})+1&n>1\end{cases}$

层数共计：$k$ 层

$k=logn$

$T(n)=O(\frac{1-4^k}{1-4})=O(4^k)=O(2^{2k})=O(2^{logn^2})=O(n^2)$

例3：

$T(n)=\begin{cases}1&n=1\\T(\frac{n}{3})+T(\frac{2n}{3})+n&n>1\end{cases}$

层数共计：$k$ 层

$k=log_{\frac{3}{2}}n$

$T(n)=O(nlog_{\frac{3}{2}}n)=O(nlogn)$

单项选择题

1.$T(n)$ 表示某个算法输入规模为n时的运算次数。如果$T(1)$ 为常数，且有递归式 $T(n)=2∗T(\frac{n}{2})+2n$，那么 $T(n)=$（ ）。

{{ select(1) }}

• $O(n)$
• $O(nlogn)$
• $O(n^2)$
• $O(n^2logn)$

2.假设某算法的计算时间表示为递推关系式

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

$T(1)=1$

则算法的时间复杂度为（ ）。

{{ select(2) }}

• $O(n)$
• $O(\sqrt{n})$
• $O(\sqrt{n}logn)$
• $O(n^2)$

3.假设某算法的计算时间表示为递推关系式

$T(n)=9T(\frac{n}{3})+n$

$T(1)=1$

则算法的时间复杂度为（ ）。

{{ select(3) }}

• $O(n)$
• $O(\sqrt{n})$
• $O(n^2)$
• $O(\sqrt{n}logn)$

4.假设某算法的计算时间表示为递推关系式

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

$T(1)=1$

则算法的时间复杂度为（ ）。

{{ select(4) }}

• $O(n)$
• $O(logn)$
• $O(n^2)$
• $O(\sqrt{n}logn)$

5.如果对于所有规模为 $n$ 的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为$O(2^n)$。

{{ select(5) }}

• $2^{n+1}$
• $3^n$
• $n2^n$
• $2^{2n}$