斐波那契数列的程序优化

[pramper]

斐波那契数列数列：0 1 1 2 3 5 8 13...，用数学公式表示为：fn(n)=fn(n-1)+fn(n-2), n>1。下面我们用js程序来实现这个算，并一步步优化它。一下程序均在Node.js v6.2.0下实现、测试。

简单的JS程序

实现斐波那契数列的程序非常简单，如下：

var count = 0  // 记录函数被调用的次数
function fib(n) {
    count++
    if(n<2) {
        return n;
    }else{
        return fib(n-1) + fib(n-2);
    }
}
fib(30)  // count=2692537，耗时16.338ms

利用记忆进行优化

可以看到，上面的程序效率之差，简直不能忍。为什么会出现这种情况呢？看下面这张图：

可以看出，执行了许多相同的运算，例如fib(3)执行了两次，fib(2)执行了三次。如果我们对中间求得的变量值，进行存储的话，就会大大减少函数被调用的次数。程序如下：

var count = 0
var tmp = [0, 1] // 存储中间求得的变量值；下标即为n
function fib(n) {
    var result = tmp[n]
    count++
    if(typeof result !== 'number') {
        result = fib(n-1) + fib(n-2)
        tmp[n] = result
    }
    return result
}
fib(30) // count=59, 耗时2.531ms

这是典型的以空间换时间。很明显，函数被调用的次数大大减少，耗时明显缩减。

动态规划

其实，我觉得最好的方法还是动态规划的方法，避免了递归调用。动态规划简单来说，就是把一个问题分解成子问题，然后求子问题的解。在斐波那契数列数列中我们可以这样想，要求fib(30)，我求出fib(29)和fib(28)就好；要求fib(29)，我求出fib(28)和fib(27)就好；要求fib(28)，我求出fib(27)和fib(26)就好...依次把问题逐渐分解最后就是求出fib(2)就好。我求出了fib(2)，再求fib(3)，再求fib(4)...直到求出fib(30)。程序如下：

var count = 0 // 技术循环次数
function fib(n) {
    var val = [0, 1]  // val[0]= fib[n-2], val[1]=fib[n-1]
    if(n<2) {
        return n
    }
    for(let i=2; i<n; i++) {
        count++
        let tmp = val[0] + val[1]
        val[0] = val[1]
        val[1] = tmp
    }
    return val[0] + val[1]
}
fib(30)  // count=28，耗时：2.552ms

总结

由变量count可以明显的看出使用动态规划性能最好。当n更大时，耗时也会比第二种方法少，可以自己试试。