complexity-theory - 阶乘递归算法的复杂性

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停止。

之后，她将 j替换为 T(n-j) + j，并获得 T(1) + n-1。

她直接说，对于n-1 = 2(log2n-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}

这条语句是正确的，因为2log2x = x对于任何非零x，因为求幂和对数是彼此的逆运算。

所以问题是:这是多项式时间还是指数时间？我将其归为伪多项式时间。如果将输入x视为数字，则运行时确实是x中的多项式。但是，多项式时间是正式定义的，因此算法的运行时间必须是关于用于指定问题输入的位数的多项式。在此，只能在Θ(log x)位中指定数字x，因此从技术上讲2log x的运行时间被视为指数时间。我在 this earlier answer中将其写为长度，建议您对其进行详细了解。

希望这可以帮助!