斐波那契数列--记忆优化减枝的效果

[vaakian]

很久以前就写过斐波那契数列的记忆优化，但并没有测试记忆优化减枝的具体效果。 通过测试，两者的差距是比较出乎我的意料的。

const mem = []
let [counter1, counter2] = [0, 0]

// 未记忆优化
const fibPrimary = n => {
    counter1++;
    if(n<=2) return 1;
    return fibPrimary(n-1) + fibPrimary(n-2);
}

// 记忆优化后
const fibOptimal = n => {
    counter2++;
    if(n <= 2) return 1;
    else {
        if(mem[n]) return mem[n];
        return mem[n] = fibOptimal(n-1) + fibOptimal(n-2);
    }
}
console.log({primary: fibPrimary(20), counter1});
console.log({optimal: fibOptimal(20), counter2});

仅仅测试到第20项结果：

{ primary: 6765, counter1: 13529 }
{ optimal: 6765, counter2: 37 }

当计算第50项时，未优化版本已经计算不出来了，而优化版本仅仅调用了98次函数，约等于非递归的循环递推法，时间复杂度为O(2n)。

{ optimal: 12586269025, counter2: 98 }