Repository navigation
斐波那契数列的程序优化 #11
Description
斐波那契数列数列：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更大时，耗时也会比第二种方法少，可以自己试试。
Activity