递归函数的运行时间T(n)

Question

我正在尝试计算这个函数的T(n),我得出的是T(n)= T(n)+ T(n)+ O(1).我有两个递归调用函数g()的拖曳T(n),然后是所有常数时间操作(如加法)的O(1).我觉得我离开了所以任何帮助都会非常感激,我的数学背景也不太合理.

int g(int y) {
 if (y <= 0) {
  return 1;
 }
 else {
  return g(y - 1) + g(y - 2);
 }
}

Answer 1

计算Fibonacci数的时间复杂度取决于所使用的算法.至少有4种算法用于计算它们(具有不同的时间复杂度):

O(\ phi ^ n)

首先我们提到我们可以通过查看递归fibonacci函数的调用图来解决这个问题.

调用图实际上是一棵树.

我们可以减少一切,找出这棵树有多少个节点.

F(n)的调用图中的节点数具有根和F(n-1)的调用图中的节点数+ F(n-2)的调用图中的节点数.

我们将用L(n)表示F(n)中的节点数(并且您将看到字母L不是偶然的).

如上所述,L(n)= L(n-1)+ L(n-2)+ 1.

但等等,还有更多!事实证明,这些正是 莱昂纳多的数字,并且它们具有一般的封闭形式:

("a(n) is the number of nodes in the Fibonacci tree of order n." A001595)

上)

还有另一种涉及记忆的算法,它具有复杂度O(n)(这里是一个例子和另一个例子).这涉及将T(n)的结果存储在矢量中并逐渐计算n = 1的T(n)直到所需的n.

如果你真的想要真正正确,那么这也不是O(n),因为加法的数量成本假定为O(1),但是......随着F(n)变大,增加的成本两个斐波那契数是O(n).你可以在这里阅读更多相关内容,这是一个很好的阐述.因此,此实现的实际复杂性为O(n ^ 2).

O(1)

还有另一种复杂度O(1)的算法,假设你使用任意精度算术或一些智能舍入.它来自Binet的公式.有关Binet公式的证明,请参见第13 页的 1.3节,使用生成函数,或者,您可以找到矩阵的特征分解,然后使用它来计算n次幂.执行此操作后,您的闭合形式公式将位于第n个幂矩阵的其中一个单元格中.

如果你想要非常精确,它实际上是O(log(n)),因为那是通过平方(也称为重复平方,二进制幂算法或二进制求幂)来计算Binet公式的指数.

通常我们假设指数x^n是O(1),但它不是,它是乘法数的O(log(n)).确切地说,您必须考虑乘法的成本,这取决于所使用的乘法算法.

这是Binet的公式btw:

以下是Fibonacci序列以矩阵形式显示的方式:

这是通过平方取幂:

更新2015-06-29:

O(日志(N))

还有另一种在O(log(n))中计算Fibonacci数的方法.有两种身份被使用

它们允许基于F(n-1),F(n),F(n )基于F(n),F(n + 1)和 F(2*n)计算F(2*n + 1)+1).该算法找到最显著位的ñ和迭代一直到最低显著位,同时使用沿着计算Fibonacci数的方式的身份.这里有算法的实现.这两个恒等式可以在二次场 ℚ(√5)中导出(如前面的链接),也可以从上面提到的矩阵的第n和第2n次幂导出(参见第2.5节"矩阵方法") "在第23页的算法计算Fibonacci数迅速'’由JL霍洛威).