0

什么是时间和空间复杂度：

int superFactorial4(int n, int m)
{
    if(n <= 1)
    {
        if(m <= 1)
            return 1;
        else 
            n = m -= 1;
    }

    return n*superFactorial4(n-1, m);
}

它通过将 n 的值减 1 直到等于 1 来递归运行，然后它将 m 的值减 1 或在 m 等于 1 的情况下返回 1。

我认为复杂性取决于 n 和 m，所以可能是 O(n*m)。

4

3 回答 3

3

时间复杂度为O(n+m^2)，空间复杂度相同。

推理：对于固定的值m，函数n对自身进行递归调用，每个都做恒定的工作，所以固定调用的复杂度m是n。现在，当 n 达到零时，它变成m-1并且m变成m-1了。因此，下一个固定 m 阶段将采用m-1，下一个m-2，依此类推。所以你得到一个(m-1)+(m-2)+...+1总和O(m^2)。

空间复杂度是相等的，因为对于每个递归调用，递归都占用恒定空间，并且您永远不会从递归返回，除非在结尾处，并且没有尾递归。

于 2009-02-10T11:32:49.770 回答
3

实际上，对我来说，它看起来更接近 O(N+m^2)。n 仅用于第一个“循环”。

此外，在任何不进行尾调用优化的语言中，空间复杂度都可能“失败”。在支持优化的语言中，空间复杂度更像 O(1)。

于 2009-02-10T11:33:27.893 回答
-1

使用递归伪代码的阶乘函数的时间复杂度：

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

time complexity;     
let T(n) be the number of steps taken to compute fact(n).


we know in each step F(n)= n*F(n-1)+C

F(n-1)= (n-1)*F(n-2)+c

substitute this in F(n), we get

F(n)= n*(n-1)*F(n-2)+(n+1)c

现在使用大 o 表示法我们可以说

F(n)>= n*F(n-1)
F(n)>= n*(n-1)*F(n-2)
.
.
.
.
.
F(n)>=n!F(n-k)

T(n)>=n!T(n-k)

n-k=1;
k=n-1;

T(n)>=n!T(n-(n-1))
T(n)>=n!T(1)
since T(1)=1
T(n)>=1*n!

现在它的形式是

 F(n)>=c(g(n))

所以我们可以说使用递归的阶乘的时间复杂度是 

T(n)= O(n!)
于 2011-09-23T14:42:06.690 回答