# 算法时间复杂度
## 一、n!
1. 作业要求
分析计算求解$n!$的递归算法和非递归算法的时间复杂度。
2. 作业内容
求$n!$的递推式为：
$$T(n)=\begin{cases}1&n=1\\n\times T(n-1)&n>1\end{cases}$$
2.1 递归算法
迭代法：先将递归算法简化为对应的递归方程，然后通过反复迭代，将递归方程的右端变换成一个级数，最后求级数的和，再估计和的渐进阶。
递归算法：
int t(int n){ if(n==1) return 1; if(n>1) return n*t(n-1); }
算法的递归方程为：
$T(n)=T(n-1)+O(1)$
迭代展开：
$\begin{aligned}T(n)&=T(n-1)+O(1)\\&=T(n-2)+O(1)+O(1)\\&=T(n-3)+O(1)+O(1)+O(1)\\&=···\\&=n\times O(1)\\&=O(n)\end{aligned}$
它的时间复杂度为$O(n)$的。
2.2非递归算法
对非递归算法的时间复杂度分析，关键式建立一个代表算法运行时间的求和表达式，然后用渐进符号表示这个求和表达式。
非递归算法：
int t(int n){ int sum=1; for(int i=1;i<=n;i++){ sum*=i; } return sum; }
算法中循环体一共执行$n$次，每次执行一条语句。所以有：
$$\sum\limits_{i=1}^n1=n$$
时间复杂度为$O(n)$
## 二、汉诺塔问题
1. 作业要求
分析计算求解汉诺塔问题的递归算法的时间复杂度。
2. 作业内容
递归算法：
设三个柱子分别时$x,y,z$,
(1) 当$n=1$时,$x$柱子只有一个盘子，可以直接移动到$z$上;
(2) 当$n>1$时，将$x$柱子上$n-1$个盘子借助$z$柱子移动到$y$上，将$x$最后一个盘子移动到$z$上，最后将$y$柱子上的盘子借助$x$柱子移动到$z$上；
void Hanoi(int n,char x,char y,char z){ if(n==1){ move(x,z);//只有一个盘子时直接移动 }else{ Hanoi(n-1,x,z,y);//将x柱子上n-1个盘子借助z柱子移动到y上 move(x,z);//将x最后一个盘子移动到z上 Hanoi(n-1,y,x,z);//将y柱子上n-1个的盘子借助x柱子移动到z上 }
假设盘子个数为$n$时，需要走$T(n)$步，将$x$柱子上的$n-1$个盘子移到$y$柱子需要$T(n-1)$步，将$x$上最后一个盘子移到$z$需要1步，将$y$柱子上$n-1$个盘子移到$z$柱子上需要$T(n-1)$步
则递推公式为：
$$T(n)=2T(n-1)+O(1)$$
迭代展开：
$$\begin{aligned}T(n)&=2T(n-1)+O(1)\\&=2(2T(n-2)+O(1))+O(1)\\&=2(2(2T(n-3)+O(1))+O(1))+O(1)\\&=···\\&=(2^{n-1}+2^{n-2}+···+2^1+1)O(1)\\&=(2^n-1)O(1)\\&=O(2^n-1)\\&=O(2^n)\end{aligned}$$
时间复杂度为$O(2^n)$
2020-09-26