为什么计算斐波那契数列的复杂度是 2^n 而不是 n^2？
我试图使用递归树找到斐波那契数列的复杂性，并得出树的高度= O(n)最坏情况，每个级别的成本= cn，因此复杂度 = n*n=n^2
怎么会是O(2^n)？
I am trying to find complexity of Fibonacci series using a recursion tree and concluded height of tree = O(n) worst case, cost of each level = cn, hence complexity = n*n=n^2
How come it is O(2^n)?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（9）
朴素递归斐波那契数列的复杂度确实是 2ⁿ。
在每个步骤中，您调用
T两次，从而提供最终的渐近屏障：T(n) = 2⋅2⋅...⋅2 = 2ⁿ奖励：斐波那契的最佳理论实现实际上是 闭合公式，使用黄金比例
：(然而，它由于浮点运算在现实生活中存在精度误差，浮点运算并不精确）
The complexity of a naive recursive fibonacci is indeed 2ⁿ.
In each step you call
Ttwice, thus will provide eventual asymptotic barrier of:T(n) = 2⋅2⋅...⋅2 = 2ⁿbonus: The best theoretical implementation to fibonacci is actually a close formula, using the golden ratio:
(However, it suffers from precision errors in real life due to floating point arithmetics, which are not exact)
fib(n) 的递归树类似于：
= 2^(n-1) - 1 + 2^(n-1)
~ 2^n
The recursion tree for fib(n) would be something like :
= 2^(n-1) - 1 + 2^(n-1)
~ 2^n
您认为树的深度是 O(n) 是正确的，但您并没有在每个级别上执行 O(n) 工作。在每个级别，每次递归调用都会执行 O(1) 工作，但每个递归调用都会贡献两个新的递归调用，一个位于其下方的级别，一个位于其下方的第二级。这意味着随着递归树的深入，每层的调用数量呈指数级增长。
有趣的是，您实际上可以将计算 F(n) 所需的准确调用次数确定为 2F(n + 1) - 1，其中 F(n) 是第 n 个斐波那契数。我们可以归纳地证明这一点。作为基本情况，要计算 F(0) 或 F(1)，我们需要对该函数进行一次调用，该函数会在不进行任何新调用的情况下终止。假设 L(n) 是计算 F(n) 所需的调用次数。然后我们就有了
现在，对于归纳步骤，假设对于所有 n' < n，其中 n ≥ 2，L(n') = 2F(n + 1) - 1。然后为了计算 F(n)，我们需要对计算 F(n) 的初始函数进行 1 次调用，其中Turn 关闭对 F(n-2) 和 F(n-1) 的调用。通过归纳假设，我们知道 F(n-1) 和 F(n-2) 可以在 L(n-1) 和 L(n-2) 调用中计算。因此总运行时间是
完成归纳。
此时，您可以使用比奈公式来证明
因此 L(n) = O(((1 + √5) / 2)n)。如果我们使用约定
我们有
且由于 φ n) 2，这是 o(2n) （使用小 o 表示法）。
有趣的是，我为这个系列选择了名称 L(n)，因为这个系列被称为 Leonardo 数。除了在这里使用之外，它还出现在 smoothsort 算法的分析中。
希望这有帮助！
You are correct that the depth of the tree is O(n), but you are not doing O(n) work at each level. At each level, you do O(1) work per recursive call, but each recursive call then contributes two new recursive calls, one at the level below it and one at the level two below it. This means that as you get further and further down the recursion tree, the number of calls per level grows exponentially.
Interestingly, you can actually establish the exact number of calls necessary to compute F(n) as 2F(n + 1) - 1, where F(n) is the nth Fibonacci number. We can prove this inductively. As a base case, to compute F(0) or F(1), we need to make exactly one call to the function, which terminates without making any new calls. Let's say that L(n) is the number of calls necessary to compute F(n). Then we have that
Now, for the inductive step, assume that for all n' < n, with n ≥ 2, that L(n') = 2F(n + 1) - 1. Then to compute F(n), we need to make 1 call to the initial function that computes F(n), which in turn fires off calls to F(n-2) and F(n-1). By the inductive hypothesis we know that F(n-1) and F(n-2) can be computed in L(n-1) and L(n-2) calls. Thus the total runtime is
Which completes the induction.
At this point, you can use Binet's formula to show that
And thus L(n) = O(((1 + √5) / 2)n). If we use the convention that
We have that
And since φ < 2, this is o(2n) (using little-o notation).
Interestingly, I've chosen the name L(n) for this series because this series is called the Leonardo numbers. In addition to its use here, it arises in the analysis of the smoothsort algorithm.
Hope this helps!
像这样看。假设通过递归计算第 k 个斐波那契数
F(k)的复杂度最多为2^k，其中kk < ;=n。这就是我们的归纳假设。那么通过递归计算F(n + 1)的复杂度为2^n + 2^(n - 1)。请注意，我们已经通过归纳证明，通过递归计算
F(k)至多2^k的说法是正确的。Look at it like this. Assume the complexity of calculating
F(k), thekthFibonacci number, by recursion is at most2^kfork <= n. This is our induction hypothesis. Then the complexity of calculatingF(n + 1)by recursion iswhich has complexity
2^n + 2^(n - 1). Note thatWe have shown by induction that the claim that calculating
F(k)by recursion is at most2^kis correct.t(n)=t(n-1)+t(n-2)
可以通过树法来解决：
最后一层类似。 。 2^n
这将使总时间复杂度=>2+4+8+.....2^n
解决上述 gp 后，我们将得到时间复杂度为 O(2^n)
t(n)=t(n-1)+t(n-2)
which can be solved through tree method:
similarly for the last level . . 2^n
it will make total time complexity=>2+4+8+.....2^n
after solving the above gp we will get time complexity as O(2^n)
斐波那契数列的复杂度为 O(F(k))，其中 F(k) 是第 k 个斐波那契数。这可以通过归纳法来证明。对于基础案例来说这是微不足道的。并假设对于所有 k<=n，计算 F(k) 的复杂度为 c*F(k) + o(F(k))，那么对于 k = n+1，计算 F(n+1) 的复杂度) 是 c*F(n) + o(F(n)) + c*F(n-1) + o(F(n-1)) = c*(F(n) + F(n-1) ) + o(F(n)) + o(F(n-1)) = O(F(n+1))。
The complexity of Fibonacci series is O(F(k)), where F(k) is the kth Fibonacci number. This can be proved by induction. It is trivial for based case. And assume for all k<=n, the complexity of computing F(k) is c*F(k) + o(F(k)), then for k = n+1, the complexity of computing F(n+1) is c*F(n) + o(F(n)) + c*F(n-1) + o(F(n-1)) = c*(F(n) + F(n-1)) + o(F(n)) + o(F(n-1)) = O(F(n+1)).
递归斐波那契数列的复杂度为2^n：
这将是递归斐波那契数列的递归关系
现在使用替换方法求解此关系（替换 T(n-1) 和 T(n-2) 的值）
再次替换上述项的值，我们将得到
完全解决后，我们get
这意味着任何级别的最大递归调用次数最多为 2^n。
对于方程 3 中的所有递归调用，时间复杂度为 ϴ(1)，因此时间复杂度为 2^n* ϴ(1)=2^n
The complexity of recursive Fibonacci series is 2^n:
This will be the Recurrence Relations for recursive Fibonacci
Now on solving this relation using substitution method (substituting value of T(n-1) and T(n-2))
Again substituting values of above term we will get
After solving it completely, we get
This implies that maximum no of recursive calls at any level will be at most 2^n.
And for all the recursive calls in equation 3 is ϴ(1) so time complexity will be
2^n* ϴ(1)=2^n斐波那契数计算的 O(2^n) 复杂度仅适用于递归方法。通过一些额外的空间，您可以使用 O(n) 获得更好的性能。
The O(2^n) complexity of Fibonacci number calculation only applies to the recursion approach. With a few extra space, you can achieve a much better performance with O(n).
我无法抗拒将 Fib 的线性时间迭代算法与指数时间递归算法联系起来的诱惑：如果有人阅读 Jon Bentley 的精彩小书“编写高效算法”，我相信这是一个简单的“缓存”案例：每当 Fib( k) 计算出来后，将其存储在数组 FibCached[k] 中。每当Fib(j)被调用时，首先检查它是否缓存在FibCached[j]中；如果是，则返回该值；如果不使用递归。 （现在看看调用树......）
I cannot resist the temptation of connecting a linear time iterative algorithm for Fib to the exponential time recursive one: if one reads Jon Bentley's wonderful little book on "Writing Efficient Algorithms" I believe it is a simple case of "caching": whenever Fib(k) is calculated, store it in array FibCached[k]. Whenever Fib(j) is called, first check if it is cached in FibCached[j]; if yes, return the value; if not use recursion. (Look at the tree of calls now ...)