algorithm - 时间和空间复杂度

Question

我对以下两种情况的时间和空间复杂度有疑问

Blockquote

案例一:

递归:阶乘计算。

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

这里时间复杂度怎么变成2*n，空间复杂度怎么变成正比于n。

和

Case II:

迭代:-

int fact(int n)
{
    int i, result = 1;
    if(n==0)
    result = 1;
    else
         {
           for(1=1;i<=n;i++)
              result*=i;
         }
     return (result);
}

时间复杂度与n成正比，空间复杂度不变。这一直让我感到困惑。

Answer 1

如果我的推理有误，请大家指正:)

对于空间复杂度，我的解释是:

对于递归求解，会有n次递归调用，所以会用到n个栈；每个电话一个。因此 O(n) 空间。这不是迭代解决方案的情况——只有一个堆栈，你甚至没有使用数组，只有一个变量。所以空间复杂度是O(1)。

对于迭代解决方案的时间复杂度，您在 for 循环中有 n 次乘法，因此松散边界将为 O(n)。其他所有操作都可以假设为单位时间或常数时间，与算法的整体效率无关。对于递归解决方案，我不太确定。如果每一步有两次递归调用，你可以把整个调用栈看成一棵平衡二叉树，节点总数为2*n - 1，但在这种情况下我我不太确定。