4

为什么递归阶乘算法的递归关系是这样的？

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...... 第二个递推关系成立（正确计算了阶乘）而不是第一个。

4

9 回答 9

11

我们一般使用递归关系来求算法的时间复杂度。

在这里，函数 T(n) 实际上并不是用于计算阶乘的值，而是告诉您阶乘算法的时间复杂度。

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

因此，对于递归阶乘算法，正确的递归关系是 T(n)=1 for n=0 T(n)=1+T(n-1) for n>0 而不是您稍后提到的。

类似河内塔的递归是 T(n)=2T(n-1)+1，对于 n>0；

更新：它通常与实施没有任何关系。但是递归可以给出编程范式的直觉，例如如果 T(n)=2*T(n/2)+n （合并排序）这给出了一种分而治之的直觉，因为我们将 n 分成两半。

此外，如果你会解方程，它会给你一个运行时间的界限。例如大哦符号。

于 2014-09-12T17:19:26.557 回答
7

看起来 T(n) 是递归阶乘算法的时间复杂度的递归关系，假设时间乘法常数。也许你误读了你的来源？

于 2009-09-04T16:59:52.460 回答
5

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

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)。
这在 big-o 表示法中被简化为 T(n) = 1 + T(n-1)。

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

于 2011-03-18T04:51:16.303 回答
4

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

于 2009-09-04T15:27:21.407 回答
3

这个问题很混乱......你的第一个公式不是阶乘。对于所有 n，它只是 T(n) = n + 1。n 的阶乘是前 n 个正整数的乘积：阶乘 (1) = 1。阶乘 (n) = n * 阶乘 (n-1)。你的第二个公式基本上是正确的。

于 2009-09-04T15:31:39.183 回答
3

T(n) = T(n-1) + 1 是 n 阶乘的正确递归方程。这个方程给你时间来计算 n 的阶乘而不是 n 的阶乘值。

于 2015-01-09T21:23:10.460 回答
2

你在哪里找到第一个？这是完全错误的。

无论值是什么，它只会每次加 1。

于 2009-09-04T15:27:59.143 回答
2

首先，您必须找到一个基本运算，对于这个例子，它是乘法。乘法在每次递归中发生一次。所以 T(n) = T(n-1) +1 这个 +1 是基本操作（这个例子中的乘法） T(n-1) 是下一个递归调用。

于 2019-04-12T18:30:21.347 回答
1

TL; DR：您问题的答案实际上取决于您的递归关系定义的顺序。也就是说，您问题中的序列T n是否代表阶乘函数或计算阶乘函数X的运行时间成本。

阶乘函数

n的阶乘f n的递归定义是：

f n = n • f n-1对于n > 0且 f 0 = 1。

正如你所看到的，上面的方程实际上是一个递推关系，因为它是一个方程，与初始项（即f 0 = 1）一起递归地定义了一个序列（即阶乘函数f n）。

对计算阶乘的运行时间成本进行建模

现在，我们将找到一个模型来表示计算n的阶乘的运行时间成本。让我们将T n称为计算f n的运行时间成本。

看看上面对阶乘函数 fn 的定义，它的运行时间成本T n将包括计算f n -1的运行时间成本（即这个成本是T n-1）加上运行时间成本执行n和f n-1之间的乘法。乘法是在恒定时间内实现的。因此我们可以说T n = T n-1 + 1。

但是，T 0的值是多少？T 0表示计算f 0的运行时间成本。由于f 0的值最初是根据定义已知的，因此计算f 0的运行时间成本实际上是恒定的。因此，我们可以说T 0 = 1。

最后，我们得到的是：

T n = T n-1 + 1对于n > 0且T 0 = 1。

上面的这个方程也是一个递推关系。然而，它所定义的（连同初始项）是一个对计算阶乘函数的运行时间成本进行建模的序列。

X考虑到如何调用递归关系中的序列（即T n），我认为它很可能代表后者，即计算阶乘函数的运行时间成本。

于 2019-01-27T14:37:01.527 回答