我正在尝试使用递归树找出斐波那契数列的复杂性,并得出树的高度 = O(n)
最坏情况,每个级别的成本 = cn
,因此 复杂性 = 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:斐波那契的最佳理论实现实际上是 close formula , 使用 golden ratio :
Fib(n) = (φⁿ – (–φ)⁻ⁿ)/sqrt(5) [where φ is the golden ratio]
(然而,由于浮点运算,它在现实生活中存在精度误差,不精确)
关于algorithm - 为什么计算斐波那契数列的复杂度是 2^n 而不是 n^2?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7547133/