0

在以下 2 个案例中，我对时间和空间复杂度有疑问

块引用

案例一：

递归：阶乘计算。

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

这里时间复杂度如何变成 2*n 和空间复杂度与 n 成正比。

和

案例二：

迭代：-

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 成正比，空间复杂度是常数。这总是让我感到困惑。

4

3 回答 3

1

如果我的推理有问题，请有人纠正我:)

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

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

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

于 2012-05-21T05:48:50.597 回答
1

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

空间复杂度

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

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

于 2016-02-18T10:45:18.050 回答
0

时间复杂度：程序在运行期间执行的（机器）指令的数量在计算机科学中称为时间复杂度。

空间复杂度：本质上是算法需要的存储单元的数量。

案例1：在程序中递归计算阶乘，所以会直接调用一次函数，然后会回溯，所以时间复杂度变成2*n。

说到空间复杂度，在程序执行的时候会声明n个栈，所以是n。

案例 2：这个案例很简单，你在 for 循环中有 n 次迭代，所以时间复杂度为 n

迭代解决方案不是这种情况——只有一个堆栈，你甚至没有使用数组，只有一个变量。所以空间复杂度是O(1)

于 2016-01-27T04:43:02.877 回答