1

所以，我在 Java 中有一个递归方法来获取第 n 个斐波那契数 - 我唯一的问题是：时间复杂度是多少？我认为它是 O(2^n)，但我可能弄错了？（我知道迭代要好得多，但这是一种练习）

public int fibonacciRecursive(int n)
{
    if(n == 1 || n == 2) return 1;
    else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
}
4

5 回答 5

5

您的递归代码具有指数运行时间。但我不认为基数是 2，而可能是黄金比例（大约 1.62）。但当然 O(1.62^n) 也自动成为 O(2^n) 。

运行时间可以递归计算：

t(1)=1
t(2)=1
t(n)=t(n-1)+t(n-2)+1

这与斐波那契数本身的递归定义非常相似。递归方程中的+1可能与大 n 无关。SI 相信它的增长速度大约与斐波那契数一样快，并且以黄金比例为基础呈指数增长。

您可以使用记忆来加速它，即缓存已经计算的结果。然后它有 O(n) 运行时间，就像迭代版本一样。

您的迭代代码的运行时间为 O(n)

您有一个简单的循环，其中包含 O(n) 步和每次迭代的恒定时间。

于 2011-01-22T15:47:50.853 回答
5

你可以用这个

替代文字

在 O(log n) 中计算 Fn

于 2011-01-22T16:18:38.230 回答
3

Each function call does exactly one addition, or returns 1. The base cases only return the value one, so the total number of additions is fib(n)-1. The total number of function calls is therefore 2*fib(n)-1, so the time complexity is Θ(fib(N)) = Θ(phi^N), which is bounded by O(2^N).

于 2011-01-22T15:59:55.047 回答
0

O(2^n)? 我在这里只看到 O(n)。

我想知道你为什么要继续计算和重新计算这些？只要内存要求不会变得太讨厌，缓存你有的不是一个好主意吗？

由于它们没有改变，如果速度对我很重要，我会生成一个表格并进行查找。

于 2011-01-22T15:50:23.233 回答
0

It's easy to see (and to prove by induction) that the total number of calls to fibonacciRecursive is exactly equal to the final value returned. That is indeed exponential in the input number.

于 2011-01-22T15:54:45.833 回答