阶乘递归算法的复杂性 [英] Complexity of factorial recursive algorithm

问题描述

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

Today in class my teacher wrote on the blackboard this recursive factorial algorithm:

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.

Then with iteration method she said that T(n-1) = T(n-2) + 2 = T(n-3) + 3 ... T(n-j) + j, so the algorithm stops when n - j = 1, so j = n - 1.

此后，她用T(n-j) + j替换为T(n-j) + j，并获得了T(1) + n-1.

After that, she substituted j in T(n-j) + j, and obtained T(1) + n-1.

她直接说，对于n-1 = 2 ^{(log ₂ n-1)}，因此算法的成本是指数级的.

She directly said that for that n-1 = 2^(log₂n-1), so the cost of the algorithm is exponential.

我真的失去了最后两个步骤.有人可以给我解释一下吗?

I really lost the last two steps. Can someone please explain them to me?

推荐答案

让我们从分析该算法开始.我们可以为已完成的工作量编写一个递归关系.作为基本情况，当算法在大小为1的输入上运行时，您需要执行一个工作单元，因此

Let's start off with the analysis of this algorithm. We can write a recurrence relation for the total amount of work done. As a base case, you do one unit of work when the algorithm is run on an input of size 1, so

T(1)= 1

T(1) = 1

对于大小为n + 1的输入，您的算法在函数本身内执行一个工作单元，然后在大小为n的输入上调用同一函数.因此

For an input of size n + 1, your algorithm does one unit of work within the function itself, then makes a call to the same function on an input of size n. Therefore

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

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

如果您扩展重复条款，您将得到

If you expand out the terms of the recurrence, you get that

• 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).

So in general this algorithm will require n units of work to complete (i.e. T(n) = n).

您的老师接下来要说的是

The next thing your teacher said was that

T(n)= n = 2 ^{log ₂ n}

T(n) = n = 2^{log₂ n}

此陈述是正确的，因为对于任何非零x，2 ^{log ₂ x} = x，因为幂和对数是彼此的逆运算.

This statement is true, because 2^log₂x = x for any nonzero x, since exponentiation and logarithms are inverse operations of one another.

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

So the question is: is this polynomial time or exponential time? I'd classify this as pseudopolynomial time. If you treat the input x as a number, then the runtime is indeed a polynomial in x. However, polynomial time is formally defined such that the runtime of the algorithm must be a polynomial with respect to the number of bits used to specify the input to the problem. Here, the number x can be specified in only Θ(log x) bits, so the runtime of 2^{log x} is technically considered exponential time. I wrote about this as length in this earlier answer, and I'd recommend looking at it for a more thorough explanation.

希望这会有所帮助！

这篇关于阶乘递归算法的复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！