时间和空间复杂

块引用

案例我的时间和空间复杂度有关的一个疑问：

Recurion：阶乘计算。

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和空间复杂度是恒定的。这总是让我感到困惑。

来源

2012-05-21 YS.

如果我的推论是错误的，有人请指正:)

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

对于递归解决方案，将有n递归调用，所以会有n使用的堆栈;每次通话一个。因此O(n)空间。迭代解决方案并非如此 - 只有一个堆栈，甚至不使用数组，只有一个变量。所以空间复杂度是O(1)。

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

来源

2012-05-21 05:48:50 Ambidextrous

的递归解决方案还将为O的时间复杂度（N ），假设乘法需要一定的时间，则重复是T（N）= T（N-1）+ O（1）。显然这意味着复杂度是O（N）的时间。 – Aravind

时间复杂度：在它的运行时间，这一个程序执行的（机器）指令的数量被称为计算机科学的时间复杂度。

空间复杂度：这基本上是其的算法需要的存储器单元的数目。

情况1：在程序是递归计算阶乘，所以会出现的功能和比会有回溯一个直接呼叫，所以时间复杂度变为2 * N。

谈到空间复杂度将有N个程序的执行点的过程中声明栈，所以它是n。

案例2：这种情况是相当简单的在这里你有n个迭代内的循环，这样的时间复杂度为n

这不是迭代求解的情况下 - 这里有一个堆栈，你连使用一个数组，只有一个变量。因此，空间复杂度为O（1）

来源

2016-01-27 04:43:02

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

空间复杂

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

空间复杂度=的函数调用数*的每个呼叫的变量数

来源

2016-02-18 10:45:18 guilhermebr

时间和空间复杂

回答

相关问题