在两种斐波纳契替代品中进行选择
在两种斐波纳契替代品中进行选择
提问于 2019-11-14 18:01:14
- 任务:在给定的index.中返回fibonacci值，例如: input：
6，返回：8。
算法1：
public static fibonacci(input: number): any {
if (input <= 1) return input;
return this.fibonacci(input - 1) + this.fibonacci(input - 2);
}时间复杂度：O(n^2)，空间复杂度：O(1)
算法2：
public static fibonacci2(input: number): any {
if (input <= 1) return input;
let a = 0;
let b = 1;
let n = 0;
for (let i=2; i<=input; i++) {
n = a + b;
a = b;
b = n;
}
return n;
}时间复杂度：O(n)，空间复杂度：O(1)
我说得对吗？
你能提出任何不同的时间和空间复杂度达到相同结果的替代方案吗？
回答 1
Code Review用户
发布于 2019-11-14 20:29:12
您可以使用时间和空间复杂度O(1)计算斐波纳契数。
(n) => ((Math.Pow(phi,n) - Math.Pow(1-phi, n)) / Math.Sqrt(5);其中phi是黄金比率：
(1 + Math.Sqrt(5)) / 2但是如果你需要一个又一个地迭代斐波那契数，我会使用一个“迭代器”，然后在O(1)中生成每一个其他的数字，它会比双公式更好。
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/232399
复制相关文章
相似问题
腾讯云开发者
