23

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

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。

之后，她代j入T(n-j) + j，得到T(1) + n-1。

她直接说对于那个 n-1 = 2 (log 2 n-1)，所以算法的代价是指数级的。

我真的失去了最后两步。有人可以向我解释一下吗？

4

1 回答 1

27

让我们从这个算法的分析开始。我们可以为完成的工作总量写一个递归关系。作为基本情况，当算法在大小为 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）。

你的老师接下来说的是

T(n) = n = 2 log 2 n

这个陈述是正确的，因为 2 log 2 x = x 对于任何非零 x，因为取幂和对数是彼此的逆运算。

所以问题是：这是多项式时间还是指数时间？我将其归类为伪多项式时间。如果将输入 x 视为一个数字，则运行时确实是 x 中的多项式。但是，多项式时间是正式定义的，因此算法的运行时间必须是关于用于指定问题输入的位数的多项式。这里，数字 x 只能以 Θ(log x) 位指定，因此 2 log x的运行时间在技术上被认为是指数时间。我在这个较早的答案中写了这个作为长度，我建议查看它以获得更彻底的解释。

希望这可以帮助！

于 2013-05-04T20:22:39.717 回答