•  21-09-2019
  •  | 
  •  

题

为什么再次发生关系的递归因子算法这个吗？

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值i。e1、2、3、4的......第二次复发有关的持有(的阶乘们正确地计算出的)不是第一个。

有帮助吗？

解决方案

这个问题很别扭......你第一个公式是不是阶乘。这只不过是T（N）= N + 1，对于所有的n。的N个因子是第一n个正整数的乘积：阶乘（1）= 1阶乘（N）= N *阶乘（N-1）。第二个公式基本上是正确的。

其他提示

像T（n）的外貌是时间复杂度递归阶乘算法，假设恒定的时间相乘的递推关系。也许你误解你的源？

我们一般使用递推关系以找到算法的时间复杂度。

这里，函数T（n）是不实际用于计算阶乘的价值，但它是告诉你约阶乘算法的时间复杂度。

它装置，用于发现N的阶乘将需要更多的操作比阶乘N-1的 （即T（N）= T（N-1）+1）等。

有一个递归阶乘算法，以便正确递推关系是 T（N）= 1，其中n = 0 T（N）= 1 + T（N-1）对于n> 0 不是说你后述。

像复发塔的河内是 T（N）= 2T（N-1）+1对于n> 0;

我假设你有不良信息。你举第二递归关系的是正确的，因为你已经观察到。第一个刚生成的自然数。

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

这只限于各任何的值是时间加1。

什么他是不是因子递归，但时间复杂性。
假设这是伪为这样的重复:

1. func factorial(n)
2.   if (n == 0)
3.      return 1
4.   return n * (factorial - 1)
  • 我假设尾递归消除不参与。

线2和3的费用一定的时间，c1和c2。
4行费用的一个固定的时间。然而，它要求因子(n-1)，这将需要一些时间T(n-1)。此外，所需的时间乘以因子(n-1)由n可以忽略一旦T(n-1)。
时间用于整个功能，只是总和：T(n)=c1+c2+T(n-1)。
这样，在大o符号，降低到T(n)=1+T(n-1)。

这是因为直径已经指出的那样，是一个平递归，因此其运转的时间应该是O(n)。它的空间复杂性将是巨大的。

T（N）= T（N-1）+ 1是用于阶乘n个正确递推方程。 这个方程给你计算阶乘N不n的阶乘的值的时间。

首先，你必须找到一个基本运行，这个例子是乘法。乘法在每一个递归发生一次。所以 T（N）= T（N-1）+1 这个1是基本的操作（mutliplication对于本示例） T（N-1）是下一个递归调用。

TL; DR：回答你的问题其实取决于什么顺序您的递推关系是定义的。也就是说，无论是序列Ť<子>名词 在你的问题表示阶乘函数或计算阶乘函数的运行时间成本 X

阶乘功能

在递归的阶乘的确定指标名词，˚F<子>名词 的，是：

˚F<子>名词 = N•˚F<子> N-1 的 N> 0 与˚F<子> 0 = 1

可以看到，上面的等式实际上是一个递推关系，因为它是一个方程的是，连同初始术语 （即，˚F<子> 0 = 1 ），递归定义的序列（即，阶乘函数，˚F<子>名词 的）。

建模计算的阶乘

磨合时间成本

现在，我们要找到的模式的用于表示计算的阶乘的磨合时间成本的名词的。让我们呼叫Ť<子>名词 的运行时间成本计算的˚F<子>名词 的。

综观上述定义阶乘函数的˚F<子>名词 的，它的运行时间成本Ť<子>名词 的将包括计算的˚F<子> N-1 的（即，这个成本Ť<子> N-1 ）加上之间执行相乘的运行时成本名词和˚F<子> N-1 的。乘法是在固定时间内实现。因此，我们可以说，Ť<子>名词 = T <子> N-1 + 1

但是，什么是Ť<子> 0 的值？ Ť<子> 0 的表示计算的运行时成本˚F<子> 0 的。由于值的˚F<子> 0 的最初通过定义已知的，用于计算运行时间成本˚F<子> 0 的是实际上不变。因此，我们可以说，Ť<子> 0 = 1

最后，我们得到的是：

Ť<子>名词 = T <子> N-1 + 1 为 N> 0 与Ť<子> 0 = 1

此方程以上也是递推关系。然而，它定义了（与初始项一起），是一个序列，其模型计算阶乘函数的运行时间成本。

X <子>考虑到如何在您的递推关系序列被称为（即牛逼<子>名词 的），我认为这很可能代表了后者，即，计算阶乘函数的运行时间成本

许可以下： CC-BY-SA 和 归因
不隶属于 StackOverflow
scroll top