我正在阅读 Skiena 的“算法设计手册”一书中的“8.1.1 递归斐波那契数”部分。
我无法理解本节中的以下段落。
此算法计算 F(n) 需要多少时间？因为 Fn+1/Fn ≈ φ = (1+√5)/2 ≈ 1.61803，这意味着 Fn > 1.6^n。因为我们的递归树有 只有 0 和 1 作为叶子，总和如此大意味着我们必须有 至少 1.6n 叶子或过程调用!这个不起眼的小程序需要指数时间才能运行!
任何人都可以从这一段中解释我的以下问题。
- 为什么用 Fn+1/Fn 来计算算法时间？
- 为什么 Fn > 1.6^n
- 我们将如何获得 1.6n 个休假或程序调用？
请以F(4)为例进行说明
最佳答案
这是我对问题的回答。
如果使用递归计算斐波那契数，计算时间为 F(N)+F(N-1)+F(N-2)+...+F(1) = F(N+2)-2 = O(F(N+2)).
Binet's Formula证明 F(N) nearly equal sqrt(1/5) * φ^N ，这个公式也证明了这一点。
- F(k+1)/F(k) 几乎等于 φ。
- 如果检查较小的 k，则可以证明 F(k) >= 1.6^k。
但我建议为该算法计算斐波那契数。
1。使用动态规划
斐波那契数列可以计算动态规划，时间为 O(N)。
这是显而易见的，因为存在 F(N)=F(N-1)+F(N-2) 的关系。
2。使用矩阵求幂
实际上，( (1 1) (1 0) )^N = ( (F(N+2) F(N+1)) (F(N+1) F(N)) ).
如果使用平方指数算法，则可以计算 O(log N) 的值，因此可以计算 O(log(N)) 的 F(N)。
综上所述，Binet的公式不好，因为它使用了浮点值，所以会导致精度误差。
我建议使用动态规划或矩阵指数对这个问题有好处。
关于algorithm - 斐波那契算法计算 F(n) 需要多少时间，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/40932355/