2

我正在尝试计算此函数的 T(n)，而我想出的是 T(n) = T(n) + T(n) + O(1)。我有两个 T(n) 用于对函数 g() 的 2 次递归调用，然后是 O(1) 用于所有恒定时间操作，例如加法。我觉得我很遥远，所以任何帮助将不胜感激，我的数学背景不太好。

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

2 回答 2

11

计算斐波那契数的时间复杂度取决于所使用的算法。至少有 4 种算法可以计算它们（具有不同的时间复杂度）：

O( \phi ^n)

首先我们提到我们可以通过查看递归斐波那契函数的调用图来解决这个问题。

调用图实际上是一棵树。

在此处输入图像描述

我们可以将所有内容简化为找出这棵树有多少个节点。

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 公式的证明，请参见第 13页的第 1.3 节，使用生成函数，或者，您可以找到矩阵的特征分解，然后使用它来计算 n 次方。完成此操作后，您的封闭式公式将位于第 n 次幂矩阵的单元格之一中。

如果你想非常精确，它实际上是 O(log(n))，因为这是你用来计算 Binet 公式的平方取幂（也称为重复平方、二进制幂算法或二进制取幂）。

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

这是Binet的公式顺便说一句：

在此处输入图像描述

以下是斐波那契数列在矩阵形式中的样子：

在此处输入图像描述

这是通过平方取幂：

在此处输入图像描述

更新 2015-06-29：

O(log(n))

在 O(log(n)) 中还有另一种计算斐波那契数的方法。有两个身份被使用

它们允许基于F(n),F(n+1)和 F(2*n)基于F(n-1),F(n),F(n)计算F(2*n+1) +1）。该算法找到n的最高有效位并向下迭代到最低有效位，同时使用沿途的恒等式来计算斐波那契数。这里有算法的实现。这两个恒等式既可以在二次域 ℚ(√5) 中导出（如上一个链接），也可以从上述矩阵的 n 次和 2n 次方导出（参见第 2.5 节标题为“矩阵方法” ”第23 页JL Holloway 的“快速计算斐波那契数的算法” ）。

于 2013-03-21T21:04:50.310 回答
0

递推关系如下：

T(n) = T(n-1) + T(n-2) + O(1)

这不适合主定理下的任何情况，因为您的方程式中没有 T(n/b) 形式的项。

因此，我们不得不采取一种有点奇怪的方法：

由于根据上述定义，T(n-1) 将等于 T(n-3) + T(n-2) + O(1)，因此您可以将 T(n) 写为：

T(n) = 2T(n-2) + T(n-3) + 2*O(1)

因为，T(n-2) = T(n-3) + T(n-4) + O(1)，我们可以进一步简化 T(n) 为：

T(n) = 3T(n-3) + 2T(n-4) + 3*O(1)

到目前为止，我们应该开始看到一种模式，但让我们更进一步了解它。由于 T(n-3) = T(n-4) + T(n-5) + O(1)：

T(n) = 5T(n-4) + 3T(n-5) + 4*O(1)

第一项的系数遵循斐波那契数列的模式。在下一轮中，我们将以 8T(n-5) 作为前导项。第二项也遵循斐波那契数列，因为在下一轮我们将有 5T(n-6)。第三项就像 n 一样增长。

所以，由于 T(1) 只是 O(1)，你最终会得到：

T(n) = x*O(1) + y*O(1) + n*O(1) 其中 x 是斐波那契数列中的第 n 项，y 是斐波那契数列中的第 (n-1) 项.

查看前面的术语，您可以看到我们的大 O 分析基本上就是基于 n 计算 x 的公式。

你可以在这里看到这个公式：http ://www.askamathematician.com/2011/04/q-is-there-a-formula-to-find-the-nth-term-in-the-fibonacci-sequence/

当您应用大 O 分析时，这将归结为以下内容：O(1.6^n)

于 2013-03-21T21:32:45.727 回答