java 斐波那契算法的时间复杂度
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/4768781/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Time Complexity of Fibonacci Algorithm
提问by Koeneuze
So, i've got a recursive method in Java for getting the 'n'th fibonacci number - The only question i have, is: what's the time complexity? I think it's O(2^n), but i may be mistaken? (I know that iterative is way better, but it's an exercise)
所以，我在 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);
}
回答by CodesInChaos
Your recursive code has exponential runtime. But I don't think the base is 2, but probably the golden ratio (about 1.62). But of course O(1.62^n) is automatically O(2^n) too.
您的递归代码具有指数运行时间。但我不认为基数是 2，而是黄金比例（大约 1.62）。但当然 O(1.62^n) 也自动是 O(2^n)。
The runtime can be calculated recursively:
运行时间可以递归计算：
t(1)=1
t(2)=1
t(n)=t(n-1)+t(n-2)+1
This is very similar to the recursive definition of the fibonacci numbers themselves. The +1in the recursive equation is probably irrelevant for large n. S I believe that it grows approximately as fast as the fibo numbers, and those grow exponentially with the golden ratio as base.
这与斐波那契数本身的递归定义非常相似。将+1在回归方程可能是无关大的n。SI 认为它的增长速度大约与 fibo 数一样快，并且以黄金比例为基础呈指数增长。
You can speed it up using memoization, i.e. caching already calculated results. Then it has O(n) runtime just like the iterative version.
您可以使用记忆加速它，即缓存已经计算的结果。然后它有 O(n) 运行时，就像迭代版本一样。
Your iterative code has a runtime of O(n)
您的迭代代码的运行时间为 O(n)
You have a simple loop with O(n) steps and constant time for each iteration.
您有一个简单的循环，每次迭代都有 O(n) 步和恒定时间。
回答by lacungus
You can use this
你可以用这个
to calculate Fn in O(log n)
以 O(log n) 计算 Fn
回答by Nabb
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).
每个函数调用只执行一次加法，或返回 1。基本情况只返回值 1，因此加法总数为 fib(n)-1。因此，函数调用的总数为 2*fib(n)-1，因此时间复杂度为 Θ(fib(N)) = Θ(phi^N)，其边界为 O(2^N)。
回答by duffymo
O(2^n)? I see only O(n) here.
哦（2^n）？我在这里只看到 O(n)。
I wonder why you'd continue to calculate and re-calculate these? Wouldn't caching the ones you have be a good idea, as long as the memory requirements didn't become too odious?
我想知道你为什么要继续计算和重新计算这些？只要内存要求不会变得太糟糕，缓存您拥有的那些不是一个好主意吗？
Since they aren't changing, I'd generate a table and do lookups if speed mattered to me.
由于它们没有改变，如果速度对我很重要，我会生成一个表并进行查找。
回答by Peter Taylor
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.
很容易看出（并通过归纳证明）对 fibonacciRecursive 的调用总数恰好等于返回的最终值。这确实是输入数字的指数。
