阶乘递归算法的复杂度

Question

今天课上老师在黑板上写了这个递归阶乘算法:

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^(log₂n-1)，所以算法的代价是指数的

最后两步我真的跑丢了。有人能给我解释一下吗?

Answer 1

让我们从分析这个算法开始。我们可以写出总做功的递归关系。作为基本情况，当算法在大小为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₂ n}

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

所以问题是:这是多项式时间还是指数时间?我把它归类为伪多项式时间。如果您将输入x视为一个数字，那么运行时间确实是x的多项式。然而，多项式时间的正式定义使得算法的运行时间必须是关于用于指定问题输入的位数的多项式。在这里，数字x只能以Θ(log x)位来指定，因此2^{log x}的运行时间在技术上被认为是指数时间。我在之前的回答中提到过这个问题，我建议你看看它，以获得更全面的解释。

希望这对你有帮助!