阶乘递归算法的复杂度

Question

阶乘递归算法的复杂度

25

今天在课堂上，我的老师在黑板上写下了这个递归阶乘算法：

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

她说它的成本为T(n-1) + 1。

然后用迭代法，她说T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j，所以当n - j = 1时算法停止，因此j = n - 1。

之后，她在T(n-j) + j中替换了j，得到T(1) + n-1。

她直接说对于n-1=2^(log2(n-1))，因此算法的成本是指数级的。

我真的不明白最后两步。有人能解释一下吗？

- Francesco Bonizzi

我想分享一个旧的线程，可以使用。线程链接 - DEBASIS PANDA

上述的函数在计算0的阶乘时会进入一个无限循环。 - Asis

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

让我们开始分析这个算法。我们可以为总工作量编写一个递归关系式。基本情况下，当算法在大小为1的输入上运行时，您会执行一单位的工作，因此

T(1) = 1

对于大小为n + 1的输入，您的算法在函数内部执行了一项工作，然后调用相同大小的函数n。因此

T(n + 1) = T(n) + 1

如果您展开递归的术语，您将得到

T(1) = 1 T(2) = T(1) + 1 = 2 T(3) = T(2) + 1 = 3 T(4) = T(3) + 1 = 4 ... T(n) = n

因此，一般来说，完成此算法需要n个工作单元（即T(n) = n）。

您的老师接下来说的是 log₂ n>这个语句是正确的，因为对于任何非零x来说，2的log以2为底的x次方等于x，因为指数和对数是互为逆运算的。

所以问题是：这是多项式时间还是指数时间？我将其分类为伪多项式时间。如果将输入x视为一个数字，则运行时间确实是关于x的多项式。然而，多项式时间的形式定义为算法的运行时间必须关于用于指定问题输入的比特数是多项式级别的。在这里，数字x可以用Θ(log x)位表示，因此2的log x次方的运行时间在技术上被认为是指数时间。我在this earlier answer中写了关于长度的内容，并建议查看它以获得更详细的解释。

希望能帮到你！