从斐波那契数列看递归和动态规划

Broadview 2019-06-27

大名鼎鼎的斐波那契数列:0,1,1,2,3,5,8,13,21...使用数学归纳法可以看出其规律为:f(n) = f(n-1) + f(n-2)

递归

下面首先直接使用递归(JavaScript实现)来求解第 n 项:f(n)

// 直接使用递归
let num = 0;    // 用来记录fib函数执行次数,执行一次加一
function fib(n) {
  num ++;
  if(n === 0) {
    return 0;
  }
  if(n === 1) {
    return 1;
  }
  return fib(n-1) + fib(n-2);
}

console.time("time used");
console.log(`result is: ${fib(40)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("time used");

以 n = 40 为例,这里我们记录了 fib 函数总共调用的次数以及运算总共耗时,结果如下:

从斐波那契数列看递归和动态规划

可以看出,即便仅仅是计算第 40 项,fib 函数调用的次数高达3亿多次,时间是2477ms。因为每一次 fib 函数的调用都会有两个子 fib 函数调用,那么时间复杂度是 O(2^n) ,呈指数级增长,这显然不是一个好算法。怎么优化呢?以一个简单的例子画图分析一下:

从斐波那契数列看递归和动态规划

上图是 n = 5 时的递归树,可以看出虚线框中 f(2) 的计算用到了三次,同样的 f(3) 的计算用到了两次,显然我们执行了非常多的重复运算。那么很自然的想到,把每一个状态的计算结果都存起来,后面遇到相同的状态就可以直接使用了。

记忆化搜索递归(自顶向下)

代码如下,这里第三行 new 了一个长度为 n+1 的数组,用于存放 f(0) 到 f(n) 这 n+1 个状态的计算结果:

// 记忆化搜索,记录每次计算的结果
let num = 0; // 用来记录fib函数执行次数,执行一次加一
let totalnum = 40;
let memory = new Array(totalnum).fill(-1);
function fib(n) {
  num++;
  if(n === 0) {
    return 0;
  }
  if(n === 1) {
    return 1;
  }
  if(memory[n] === -1) {
    memory[n] = fib(n-1) + fib(n-2);  // 如果前面已经得到,直接使用
  } 
  return memory[n];
}

console.time("timer");
console.log(`result is: ${fib(totalnum)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("timer");

同样 n = 40,结果如下:

从斐波那契数列看递归和动态规划

可以看处出优化是十分可观的,记录下每一次子调用的结果,让算法复杂度从 O(2^n) 变成了 O(n)。这其实就是动态规划的思想。什么是动态规划?

Dynamic programming is when you use past knowledge to make solving a future problem easier.(动态规划是用已知项去更好的求解未知项)
Dynamic programming is a technique used to avoid computing multiple time the same subproblem in a recursive algorithm.
将原问题拆解成若干子问题,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。

以上是我看到的两个很好的定义。记忆化搜索递归求斐波那契数列显然是使用了动态规划的思想,并且,这是一种自顶向下的求解方式(我们没有从最基本的问题开始求解,对于 f(n) = f(n-1) + f(n-2) ,先假定 f(n-1) f(n-2) 是已知的)。另外我们可以采用另一种自下向上的方式求解,即迭代,这也是一种动态规划的思想。

迭代法(自下向上)

代码如下,我们使用迭代,f(2) = f(1) + f(0),f(3) = f(2) + f(1),...,显然这是一种从基础问题开始的自下向上的解决方法:

let num = 0;
function fib(n) {
  num++;
  let memory = new Array(n);
  memory[0] = 1;
  memory[1] = 1;
  for(let i = 2; i <= n; i++) {
    memory[i] = memory[i-1] + memory[i-2];  
  }
  return memory[n];
}

console.time("timer");
console.log(`result is: ${fib(40)}`);
console.log(`fib() runned ${num} times`);
console.timeEnd("timer");

结果如下,显然使用迭代的方法复杂度也为 O(n):

从斐波那契数列看递归和动态规划

小结

动态规划就是:将原问题拆解成若干子问题,同时保存子问题的答案,使得每个子问题只求解一次,最终获得原问题的答案。对于斐波那契数列的求解,有自顶向下的记忆化搜索递归和自下向上的迭代法,他们都使用了动态规划的思想。

参考链接:
https://stackoverflow.com/que...

相关推荐