二、(25分)阅读下面的阶乘函数的递归算法,写出递推公式,并展开通推公式,求解时间复杂度。 Int Fact (int n). if(n==1) return 1; Else return n*Fact(n-1):
时间: 2024-05-30 22:10:50 浏览: 12
递推公式:$f(n) = n \times f(n-1)$
展开通推公式:
$$
\begin{aligned}
f(n) &= n \times f(n-1) \\
&= n \times (n-1) \times f(n-2) \\
&= n \times (n-1) \times (n-2) \times f(n-3) \\
&\cdots \\
&= n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 \\
&= n!
\end{aligned}
$$
时间复杂度:$O(n)$。因为需要递归调用 $n$ 次,每次调用的时间复杂度为 $O(1)$,所以总的时间复杂度为 $O(n)$。
相关问题
n的阶乘递归与非递归时间复杂度的推导
n的阶乘递归算法的时间复杂度为O(N),因为每次递归的时间复杂度为O(1),但递归的总次数为N次,所以 N*O(1)=O(N)。而n的阶乘非递归算法的时间复杂度也为O(N),因为需要进行N次乘法运算。
相比之下,斐波那契数列的递归算法时间复杂度为O(2^N),因为每次递归调用时,时间是不可重复利用的,一去不复返,所以复杂度极高。
至于n的阶乘递归与非递归算法的空间复杂度,n的阶乘递归算法的空间复杂度为O(N),因为需要N次递归调用,每次调用都需要保存一些信息。而n的阶乘非递归算法的空间复杂度为O(1),因为只需要保存一个变量即可。
设计算法求解正整数n的阶乘,并分析其时间复杂度以及空间复杂度
可以使用递归算法来求解n的阶乘,其时间复杂度为O(n),空间复杂度为O(n),其算法实现如下:long factorial(int n)
{
if (n == 1)
return 1;
else
return n * factorial(n-1);
}
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)