为什么计算斐波那契数列2 ^ n而不是n ^ 2的复杂性？
我试图使用递归树找到斐波那契数列的复杂度并得出height of tree = O(n)最坏情况cost of each level =
cn，因此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ⁿ
：最好理论实施斐波纳契实际上是一个接近式，使用黄金比例：
Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]（但是，由于浮点运算，它在现实生活中会遇到精度误差，这是不准确的）
以上是 为什么计算斐波那契数列2 ^ n而不是n ^ 2的复杂性？ 的全部内容， 来源链接： utcz.com/qa/423107.html
