时间和空间复杂性

Question

在以下两个案例中，我对时间和空间复杂性有疑问。

区块报价

案例I:

递推:阶乘计算。

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)。

对于迭代解决方案的时间复杂性，在n循环中有for乘法，因此一个松散的界限将是O(n)。每一种操作都可以假定为单位时间或恒定时间，对算法的整体效率没有影响。对于递归解决方案，我不太确定。如果每个步骤都有两个递归调用，则可以将整个调用堆栈看作一个平衡的二叉树，节点总数将为2*n - 1，但在这种情况下，我不太确定。

Answer 2

来自：https://cs.nyu.edu/~acase/fa14/CS2/module_extras.php

空间复杂性

下面，我们将比较三个不同的调用与迭代和递归阶乘函数，并查看如何使用内存。请记住，我们声明的每个变量都必须在内存中保留空间来存储它的数据。因此，最简单形式的算法的空间复杂性是使用的变量数。因此，在这种最简单的情况下，我们可以使用这个方程计算近似空间复杂度：

空间复杂度=函数调用数*每次调用的变量数

Answer 3

时间复杂性:在计算机科学中，程序在运行期间执行的(机器)指令的数量，称为时间复杂度。

空间复杂性:这本质上是一个算法需要的内存单元数。

案例1:在程序中是递归计算阶乘的，所以会有一个函数的直接调用，而不是回溯，所以时间复杂度变成2*n。

说到空间的复杂性，在程序执行过程中会声明n个堆栈，所以它就是n。

案例2:这个例子非常简单，在for循环中有n个迭代，所以时间复杂度为n。

迭代解决方案不是这样的--只有一个堆栈，而且您甚至没有使用数组，只有一个变量。所以空间复杂度是O(1)。