我试图使用递归树找到斐波那契数列的复杂性并得出结论height of tree = O(n)最坏的情况下，cost of each level = cn, hence complexity = n*n=n^2
怎么会这样O(2^n)?
朴素递归斐波那契的复杂度确实是 2ⁿ。
T(n) = T(n-1) + T(n-2) = T(n-2) + T(n-3) + T(n-3) + T(n-4) =
= T(n-3) + T(n-4) + T(n-4) + T(n-5) + T(n-4) + T(n-5) + T(n-5) + T(n-6) = ...
在你调用的每一步中T两次，因此将提供最终的渐近屏障：
T(n) = 2⋅2⋅...⋅2 = 2ⁿ
bonus：斐波那契的最佳理论实现实际上是封闭公式 http://en.wikipedia.org/wiki/Fibonacci_number#Matrix_form， 使用黄金比例 http://en.wikipedia.org/wiki/Golden_ratio:
Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]
（然而，由于浮点运算并不精确，它在现实生活中会出现精度误差）
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
