如何用JavaScript实现O(n)时间复杂度的第n项斐波那契数求解

嘿，我来帮你搞定这个问题！你的代码出现无限循环和栈溢出的核心原因是全局变量k——递归过程中多个调用会共享这个变量，导致后续的递归调用使用了错误的k值，进而陷入无限递归，最终触发调用栈溢出。

第一步：修复你的递归代码 #

只需要把k从全局变量改成函数内部的局部变量，就能解决无限循环问题：

const MAX = 1000;
let f = Array(MAX).fill(0);

const fib = (n) => {
    if (n === 0) {
        return 0;
    }
    if (n === 1 || n === 2) {
        f[n] = 1;
        return f[n];
    }
    if (f[n]) {
        return f[n];
    }
    // 把k改为局部变量，避免递归调用互相干扰
    const k = n & 1 ? Math.floor((n + 1) / 2) : Math.floor(n / 2);
    
    if (n & 1) {
        f[n] = fib(k) * fib(k) + fib(k - 1) * fib(k - 1);
    } else {
        f[n] = (2 * fib(k - 1) + fib(k)) * fib(k);
    }
    return f[n];
};

console.log(fib(9)); // 输出34，正常运行

不过要注意，这个递归版本用了斐波那契的快速计算公式，时间复杂度其实是O(logn)，比你想要的O(n)更高效，但递归深度还是会随着n增大而增加，极端情况下还是可能出现栈溢出。

第二步：实现时间复杂度为O(n)的斐波那契求解（迭代版本） #

如果明确需要O(n)时间复杂度，最稳妥且无栈溢出风险的方式是用迭代法，从底向上计算，只需要维护两个变量保存前两项的值，空间复杂度还能优化到O(1)：

const fib = (n) => {
    // 基准情况处理
    if (n === 0) return 0;
    if (n === 1 || n === 2) return 1;
    
    let prevPrev = 1; // 第n-2项
    let prev = 1;     // 第n-1项
    let current;
    
    // 从第3项开始迭代到第n项
    for (let i = 3; i <= n; i++) {
        current = prevPrev + prev;
        prevPrev = prev;
        prev = current;
    }
    
    return current;
};

console.log(fib(9)); // 输出34
console.log(fib(1000)); // 可以正常计算大数值，不会栈溢出

为什么这个版本是O(n)？ #

• 循环从3到n一共执行了n-2次，时间复杂度是线性的O(n)
• 只使用了几个变量，空间复杂度是O(1)，非常高效
• 完全没有递归调用，不会出现调用栈溢出的问题

如果你需要保存所有计算过的斐波那契数（比如后续还要用到），也可以用数组存储，空间复杂度变成O(n)：

const fib = (n) => {
    if (n === 0) return 0;
    const fibArr = [0, 1, 1]; // 索引对应第n项，fibArr[0]=0（第0项），fibArr[1]=1（第1项）
    
    for (let i = 3; i <= n; i++) {
        fibArr[i] = fibArr[i-1] + fibArr[i-2];
    }
    
    return fibArr[n];
};

console.log(fib(9)); // 输出34

总结一下：如果追求O(n)时间复杂度，迭代法是最可靠的选择，避免了递归带来的栈溢出风险，代码也更直观易懂。

内容的提问来源于stack exchange，提问作者iremlopsum