我正在尝试通过优化算法和理解 big-o 等变得更好。
我将以下函数放在一起计算第 n 个斐波那契数。这有效(对于相当高的输入)。我的问题是,我该如何改进这个功能?这样计算斐波那契数列有什么弊端?
function fibo(n) {
var i;
var resultsArray = [];
for (i = 0; i <= n; i++) {
if (i === 0) {
resultsArray.push(0);
} else if (i === 1) {
resultsArray.push(1);
} else {
resultsArray.push(resultsArray[i - 2] + resultsArray[i - 1]);
}
}
return resultsArray[n];
}
我相信我的时间大 o 是 O(n),但由于我创建的数组,我的空间大 o 是 O(n^2)。这是正确的吗?
最佳答案
如果您没有数组,那么您可以节省内存和.push
调用
function fib(n) {
var a = 0, b = 1, c;
if (n < 3) {
if (n < 0) return fib(-n);
if (n === 0) return 0;
return 1;
}
while (--n)
c = a + b, a = b, b = c;
return c;
}
关于javascript - 在 Javascript 中计算斐波那契数列的最有效方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29973567/