关于运行效率的一个简单的有关问题

关于运行效率的一个简单的问题
下面这两个代码都是实现n * (n-1) * (n -2)* ...*2*1
一种是递归，一种是普通方法，我感觉普通方法时间复杂度低，为什么面试官貌似不同意？（但是他没跟我说答案）
希望大家觉得那个时间复杂度低给出原因，谢谢~
Code 1：递归

C/C++ code

#include<stdio.h>int fuck(int n){    int sum = 1;    if(n == 1)    {        return 1;    }    sum = n * fuck(n - 1);    return sum;}int main(){    int n;    int sum = 0;        scanf("%d",&n);    sum = fuck(n);    printf("%d",sum);    return 0;}

Code2：普通

C/C++ code

#include<stdio.h>int fuck(int n){    int sum = 1;    while(n > 1)    {        sum = sum * n;        n--;    }    return sum;}int main(){    int n;    int sum;        scanf("%d",&n);    sum = fuck(n);    printf("%d",sum);    return 0;}

[解决办法]
两个时间复杂度都是O(n)，但是递归算法还需要O(n)的栈空间。
[解决办法]
迭代算法的时间复杂度是O(n)很容易理解。
而递归算法的递归式为：
T(0) = O(1);
T(n) = T(n - 1) + O(1);
转换一下得：
T(n) - T(n - 1) = O(1)
T(n - 1) - T(n - 2) = O(1)
....
T(1) - T(0) = O(1)
-------------
两边加起来解得
T(n) = n * O(1) = O(n)

------------
所以迭代算法和递归算法时间复杂度都是一样的。
但是递归算法需要O(n)的栈空间

查看更多 下一篇