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]
(但是,由于浮点运算,它在现实生活中会遇到精度误差,这是不准确的)
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)