添加 Memoization 后斐波那契计算变慢 Javascript

Question

比较两个版本，似乎使用记忆化的版本在理论上应该更快的时候更慢。为什么会这样？

没有记忆：

function fibonacci(n) {
    if (n <= 1) {
        return 1;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}
const start = Date.now();
fibonacci(22);
const duration = Date.now() - start;
console.log(duration);

输出：`11`

有记忆功能：

function fibonacci(n, dic = {}) {
    if (n <= 1) {
        return 1;
    }
    if (dic[n]) {
        return dic[n];
    }
    let res = fibonacci(n - 1) + fibonacci(n - 2);
    dic[n] = res
    return res
}

const start = Date.now();
fibonacci(22);
console.log(Date.now() - start);

输出：`19`

Answer 1

在您的记忆版本中，您忘记将 dic 传递到递归调用堆栈。所以它每次都会得到默认值。

当你通过它时，时间在我的机器上降为零（这种测量性能的方法不是特别准确 - 显然它不是零！）

function fibonacci(n, dic = {}) {
    if (n <= 1) {
        return 1;
    }
    if (dic[n]) {
        return dic[n];
    }
    let res = fibonacci(n - 1,dic) + fibonacci(n - 2,dic);
    dic[n] = res
    return res
}

const start = Date.now();
fibonacci(22);
console.log(Date.now() - start);

添加 Memoization 后斐波那契计算变慢 Javascript

Computing for Fibonacci becomes slower after adding Memoization Javascript

javascript

algorithm

recursion

performance

memoization

输出：`11`

输出：`19`

添加 Memoization 后斐波那契计算变慢 Javascript

Computing for Fibonacci becomes slower after adding Memoization Javascript

javascript

algorithm

recursion

performance

memoization

输出：11

输出：19

输出：`11`

输出：`19`