递归关系

Question

为什么递归因子算法的递归关系呢？

T(n)=1 for n=0
T(n)=1+T(n-1) for n>0

为什么不是这个？

T(n)=1 for n=0
T(n)=n*T(n-1) for n>0

将n即1,2,3,4 ......的值置于第二个递归关系(正确计算因子)不是第一个.

Answer 1

看起来T(n)是递归因子算法的时间复杂度的递归关系,假设恒定时间乘法.也许你误读了你的来源？

Answer 2

我们通常使用递归关系来找出算法的时间复杂度.

这里,函数T(n)实际上不是用于计算阶乘的值,而是告诉你阶乘算法的时间复杂度.

这意味着找到n的阶乘,它将比n-1的阶乘(即T(n)= T(n-1)+ 1)需要多1次操作,依此类推.

所以递归因子算法的正确递归关系是T(n)= 1,n = 0 T(n)= 1 + T(n-1),n> 0,这不是你后面提到的.

像河内塔的复发一样,对于n> 0,T(n)= 2T(n-1)+1;

Answer 3

我假设你有不好的信息.正如您所观察到的,您引用的第二个递归关系是正确的.第一个只生成自然数.

Answer 4

他提出的不是阶乘递归，而是它的时间复杂度。
假设这是这种重复的伪代码：

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)

• 我假设不涉及尾递归消除。

第 2 行和第 3 行花费恒定时间 c1 和 c2。
第 4 行的时间也是恒定的。但是，它调用 factorial(n-1) 需要一些时间 T(n-1)。此外，一旦使用 T(n-1)，可以忽略将 factorial(n-1) 乘以 n 所需的时间。
整个函数的时间就是总和：T(n) = c1 + c2 + T(n-1)。
这在大 o 符号中被简化为 T(n) = 1 + T(n-1)。

正如 Diam 指出的那样，这是一个平面递归，因此它的运行时间应该是 O(n)。但它的空间复杂度将是巨大的。