斐波那契算法的时间复杂度
所以，我在 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);
}
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)
public int fibonacciRecursive(int n)
{
if(n == 1 || n == 2) return 1;
else return fibonacciRecursive(n-2) + fibonacciRecursive(n-1);
}
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（5）
您的递归代码具有指数运行时间。但我不认为底数是2，而可能是黄金比例（大约1.62）。但当然 O(1.62^n) 也自动是 O(2^n) 。
运行时间可以递归计算：
这与斐波那契数本身的递归定义非常相似。递归方程中的 +1 可能与大 n 无关。 SI 相信它的增长速度大约与斐波那契数一样快，并且以黄金比例为基础呈指数增长。
您可以使用记忆来加速它，即缓存已经计算的结果。然后它有 O(n) 运行时间，就像迭代版本一样。
您的迭代代码的运行时间为 O(n)
您有一个简单的循环，其中每次迭代的步骤为 O(n) 且时间恒定。
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.
The runtime can be calculated recursively:
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.You can speed it up using memoization, i.e. caching already calculated results. Then it has O(n) runtime just like the iterative version.
Your iterative code has a runtime of O(n)
You have a simple loop with O(n) steps and constant time for each iteration.
您可以使用此
计算 O(log n) 中的 Fn
You can use this
to calculate Fn in O(log n)
每个函数调用恰好执行一次加法，或返回 1。基本情况仅返回值 1，因此加法总数为 fib(n)-1。因此，函数调用总数为 2*fib(n)-1，因此时间复杂度为 θ(fib(N)) = θ(phi^N)，其边界为 O(2^N)。
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).
O(2^n)？我在这里只看到 O(n) 。
我想知道为什么你还要继续计算并重新计算这些？只要内存要求不变得太令人讨厌，缓存您拥有的内容不是一个好主意吗？
由于它们没有改变，如果速度对我很重要，我会生成一个表并进行查找。
O(2^n)? I see only O(n) here.
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.
很容易看出（并通过归纳证明）对 fibonacciRecursive 的调用总数恰好等于返回的最终值。这确实是输入数量的指数。
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.