本文實(shí)例講述了JavaScript程序設(shè)計(jì)高級(jí)算法之動(dòng)態(tài)規(guī)劃。分享給大家供大家參考，具體如下：

主要是看了《數(shù)據(jù)結(jié)構(gòu)與算法》有所感悟，雖然這本書被挺多人詬病的，說(shuō)這有漏洞那有漏洞，但并不妨礙我們從中學(xué)習(xí)知識(shí)。

其實(shí)像在我們前端的開發(fā)中，用到的高級(jí)算法并不多，大部分情況if語(yǔ)句，for語(yǔ)句，swith語(yǔ)句等等，就可以解決了。稍微復(fù)雜的，可能會(huì)想到用遞歸去的解決。

但要注意的是遞歸寫起來(lái)簡(jiǎn)潔，但實(shí)際上執(zhí)行的效率并不高。

我們?cè)倏纯磩?dòng)態(tài)規(guī)劃的算法：

動(dòng)態(tài)規(guī)劃解決方案從底部開始解決問(wèn)題， 將所有小問(wèn)題解決掉， 然后合并成一個(gè)整體解決方案， 從而解決掉整個(gè)大問(wèn)題 。

實(shí)例舉例  （計(jì)算斐波那契數(shù)列）

斐波那契數(shù)列指的是這樣一個(gè)數(shù)列 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233，377，610，987，1597，2584，4181，6765，10946，17711，28657，46368........

這個(gè)數(shù)列從第3項(xiàng)開始，每一項(xiàng)都等于前兩項(xiàng)之和。

針對(duì)這個(gè)數(shù)列，可以用一個(gè)遞歸的函數(shù)去計(jì)算第n項(xiàng) 數(shù)值

// 斐波那契數(shù)列
function recurFib(n) {
    if(n < 2){
      return n ;
    }else {
//          document.write("第"+(n-1)+"次計(jì)算&nbsp;n-1="+(n-1)+recurFib(n-1)+'&nbsp;&nbsp;&nbsp;');
//          document.write("n-2="+(n-2)+recurFib(n-2)+"<br>");
      return recurFib(n-1)+recurFib(n-2)
    }
}

確實(shí)是個(gè)非常簡(jiǎn)潔的代碼，上面有被注釋的代碼 ，是用來(lái)打印出當(dāng)n=多少，要執(zhí)行多少次函數(shù)，不過(guò)明眼人一眼就能看出來(lái)執(zhí)行的次數(shù)隨著n的變大，次數(shù)也會(huì)非常恐怖增長(zhǎng)。

當(dāng)n=5的時(shí)候，遞歸樹已經(jīng)長(zhǎng)的很大了……可以預(yù)見當(dāng)n=10，甚至n=100的時(shí)候……

明白了遞歸函數(shù)執(zhí)行效率之差，我們?cè)賮?lái)看的動(dòng)態(tài)規(guī)劃是如何做的

function dynFib(n) {
  let val = [];
  for(let i = 0; i <= n; ++i){
    val[i]=0;
  }
  if(n ===1 || n === 2){
    return 1;
  }
  else {
    val[1] =1;
    val[2] = 2;
    for(let i = 3; i <= n; ++i){
      val[i] = val [i-1] +val[i-2] ;
    }
  }
  return val[n-1]
}

通過(guò)數(shù)組 val 中保存了中間結(jié)果， 如果要計(jì)算的斐波那契數(shù)是 1 或者 2， 那么 if 語(yǔ)句會(huì)返回 1。 否則，數(shù)值 1 和 2 將被保存在 val 數(shù)組中 1 和 2 的位置。

循環(huán)將會(huì)從 3 到輸入的參數(shù)之間進(jìn)行遍歷， 將數(shù)組的每個(gè)元素賦值為前兩個(gè)元素之和， 循環(huán)結(jié)束， 數(shù)組的最后一個(gè)元素值即為最終計(jì)算得到的斐波那契數(shù)值， 這個(gè)數(shù)值也將作為函數(shù)的返回值。

接下來(lái)可以寫個(gè)簡(jiǎn)單的測(cè)試函數(shù)，來(lái)對(duì)比兩者的運(yùn)行時(shí)間。

// 定義一個(gè)測(cè)試函數(shù)，將待測(cè)函數(shù)作為參數(shù)傳入
function test(func,n){
  let start = new Date().getTime();//起始時(shí)間
  let res = func(n);//執(zhí)行待測(cè)函數(shù)
  document.write('<br>'+'當(dāng)n='+n+'的時(shí)候&nbsp;'+res+'<br>');
  let end = new Date().getTime();//結(jié)束時(shí)間
  return (end - start)+"ms";//返回函數(shù)執(zhí)行需要時(shí)間
}

打印函數(shù)執(zhí)行

let time = test(recurFib,40);
document.write(time);
let time2 = test(dynFib,40);
document.write(time2);

結(jié)果如下：

最后， 你或許已經(jīng)意識(shí)到在使用迭代的方案計(jì)算斐波那契數(shù)列時(shí)， 是可以不使用數(shù)組的。

需要用到數(shù)組的原因是因?yàn)閯?dòng)態(tài)規(guī)劃算法通常需要將中間結(jié)果保存起來(lái)。

以下是迭代版本的斐波那契函數(shù)義

function iterFib(n) {
  let last = 1;
  let nextLast = 1;
  let result = 1;
  for (let i = 2; i < n; ++i) {
    result = last + nextLast;
    nextLast = last;
    last = result;
  }
  return result;
}

當(dāng)然這個(gè)迭代版本的與數(shù)組的版本的效率也是相同的。

更多關(guān)于JavaScript相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《JavaScript數(shù)據(jù)結(jié)構(gòu)與算法技巧總結(jié)》、《JavaScript數(shù)學(xué)運(yùn)算用法總結(jié)》、《JavaScript排序算法總結(jié)》、《JavaScript遍歷算法與技巧總結(jié)》、《JavaScript查找算法技巧總結(jié)》及《JavaScript錯(cuò)誤與調(diào)試技巧總結(jié)》

希望本文所述對(duì)大家JavaScript程序設(shè)計(jì)有所幫助。

最新評(píng)論