從斐波那契數(shù)列看遞歸和動(dòng)態(tài)規(guī)劃

charles_paul 發(fā)布于2019-08-22 18:30 / 2730人閱讀

摘要：大名鼎鼎的斐波那契數(shù)列，，，，，，，，使用數(shù)學(xué)歸納法可以看出其規(guī)律為。對(duì)于斐波那契數(shù)列的求解，有自頂向下的記憶化搜索遞歸和自下向上的迭代法，他們都使用了動(dòng)態(tài)規(guī)劃的思想。

大名鼎鼎的斐波那契數(shù)列：0，1，1，2，3，5，8，13，21...使用數(shù)學(xué)歸納法可以看出其規(guī)律為：f(n) = f(n-1) + f(n-2)。

遞歸

下面首先直接使用遞歸（JavaScript實(shí)現(xiàn)）來(lái)求解第 n 項(xiàng)：f(n)

// 直接使用遞歸
let num = 0;    // 用來(lái)記錄fib函數(shù)執(zhí)行次數(shù)，執(zhí)行一次加一
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 函數(shù)總共調(diào)用的次數(shù)以及運(yùn)算總共耗時(shí)，結(jié)果如下：

可以看出，即便僅僅是計(jì)算第 40 項(xiàng)，fib 函數(shù)調(diào)用的次數(shù)高達(dá)3億多次，時(shí)間是2477ms。因?yàn)槊恳淮?fib 函數(shù)的調(diào)用都會(huì)有兩個(gè)子 fib 函數(shù)調(diào)用，那么時(shí)間復(fù)雜度是 O(2^n) ，呈指數(shù)級(jí)增長(zhǎng)，這顯然不是一個(gè)好算法。怎么優(yōu)化呢？以一個(gè)簡(jiǎn)單的例子畫圖分析一下：

上圖是 n = 5 時(shí)的遞歸樹，可以看出虛線框中 f(2) 的計(jì)算用到了三次，同樣的 f(3) 的計(jì)算用到了兩次，顯然我們執(zhí)行了非常多的重復(fù)運(yùn)算。那么很自然的想到，把每一個(gè)狀態(tài)的計(jì)算結(jié)果都存起來(lái)，后面遇到相同的狀態(tài)就可以直接使用了。

記憶化搜索遞歸(自頂向下)

代碼如下，這里第三行 new 了一個(gè)長(zhǎng)度為 n+1 的數(shù)組，用于存放 f(0) 到 f(n) 這 n+1 個(gè)狀態(tài)的計(jì)算結(jié)果：

// 記憶化搜索，記錄每次計(jì)算的結(jié)果
let num = 0; // 用來(lái)記錄fib函數(shù)執(zhí)行次數(shù)，執(zhí)行一次加一
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);  // 如果前面已經(jīng)得到，直接使用
  } 
  return memory[n];
}

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

同樣 n = 40，結(jié)果如下：

可以看處出優(yōu)化是十分可觀的，記錄下每一次子調(diào)用的結(jié)果，讓算法復(fù)雜度從 O(2^n) 變成了 O(n)。這其實(shí)就是動(dòng)態(tài)規(guī)劃的思想。什么是動(dòng)態(tài)規(guī)劃？

Dynamic programming is when you use past knowledge to make solving a future problem easier.(動(dòng)態(tài)規(guī)劃是用已知項(xiàng)去更好的求解未知項(xiàng))

Dynamic programming is a technique used to avoid computing multiple time the same subproblem in a recursive algorithm.

將原問(wèn)題拆解成若干子問(wèn)題，同時(shí)保存子問(wèn)題的答案，使得每個(gè)子問(wèn)題只求解一次，最終獲得原問(wèn)題的答案。

以上是我看到的兩個(gè)很好的定義。記憶化搜索遞歸求斐波那契數(shù)列顯然是使用了動(dòng)態(tài)規(guī)劃的思想，并且，這是一種自頂向下的求解方式（我們沒(méi)有從最基本的問(wèn)題開(kāi)始求解，對(duì)于 f(n) = f(n-1) + f(n-2) ，先假定 f(n-1) 和 f(n-2) 是已知的）。另外我們可以采用另一種自下向上的方式求解，即迭代，這也是一種動(dòng)態(tài)規(guī)劃的思想。

迭代法(自下向上)

代碼如下，我們使用迭代，f(2) = f(1) + f(0),f(3) = f(2) + f(1),...，顯然這是一種從基礎(chǔ)問(wèn)題開(kāi)始的自下向上的解決方法：

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");

結(jié)果如下，顯然使用迭代的方法復(fù)雜度也為 O(n)：

小結(jié)

動(dòng)態(tài)規(guī)劃就是：將原問(wèn)題拆解成若干子問(wèn)題，同時(shí)保存子問(wèn)題的答案，使得每個(gè)子問(wèn)題只求解一次，最終獲得原問(wèn)題的答案。對(duì)于斐波那契數(shù)列的求解，有自頂向下的記憶化搜索遞歸和自下向上的迭代法，他們都使用了動(dòng)態(tài)規(guī)劃的思想。

參考鏈接：
https://stackoverflow.com/que...