阶乘递归算法的复杂性

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 ^{(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}

这句话是正确的,因为对于任何非零x,2 ^{log ₂ x} = x,因为取幂和对数是彼此的逆运算.

所以问题是:这是多项式时间还是指数时间？我把它归类为伪多项式时间.如果将输入x视为数字,则运行时确实是x中的多项式.然而,正式定义多项式时间,使得算法的运行时必须是关于用于指定问题输入的位数的多项式.这里,数字x只能用Θ(log x)位指定,因此2 ^{log x}的运行时间在技术上被认为是指数时间.我在这个早期的答案中写了这篇文章的长度,我建议你查看它以获得更全面的解释.

希望这可以帮助!