首頁  >  文章  >  web前端  >  JS動態規劃使用詳解

JS動態規劃使用詳解

php中世界最好的语言
php中世界最好的语言原創
2018-04-14 13:56:421776瀏覽

這次帶給大家JS動態規劃使用詳解,JS動態規劃使用的注意事項有哪些,以下就是實戰案例,一起來看一下。

其實像在我們前端的開發中,用到的高階演算法不多,大部分情況if語句,for語句,swith語句等等,就可以解決了。稍微複雜的,可能會想到用遞歸的解決。

# 但要注意的是遞歸寫起來簡潔,但實際上執行的效率並不高。

我們再來看看動態規劃的演算法:

動態規劃解決方案從底部開始解決問題, 將所有小問題解決掉, 然後合併成一個整體解決方案, 從而解決掉整個大問題 。

實例舉例  (計算斐波那契數列)

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

# 這個數列從第3項開始,每一項都等於前兩項之和。

針對這個數列,可以用一個遞迴的函數去計算第n項 數值

// 斐波那契数列
function recurFib(n) {
    if(n ");
      return recurFib(n-1)+recurFib(n-2)
    }
}

確實是個非常簡潔的程式碼,上面有被註解的程式碼,是用來印出當n=多少,要執行多少次函數,不過明眼人一眼就能看出來執行的次數隨著n的變大,次數也會非常恐怖成長。

JS動態規劃使用詳解

# 當n=5的時候,遞迴樹已經長的很大了…可以預見當n=10,甚至n=100的時候…

明白了遞迴函數執行效率之差,我們再來看的動態規劃是如何做的

function dynFib(n) {
  let val = [];
  for(let i = 0; i <p style="text-align: left;">
透過數組 val 中保存了中間結果, 如果要計算的斐波那契數是 1 或 2, 那麼 if 語句會傳回 1。否則,數值 1 和 2 將被保存在 val 數組中 1 和 2 的位置。 </p><p style="text-align: left;">
循環將會從3 到輸入的參數之間進行遍歷, 將數組的每個元素賦值為前兩個元素之和, 循環結束, 數組的最後一個元素值即為最終計算得到的斐波那契數值,這個數值也將作為<a href="http://www.php.cn/code/6029.html" target="_blank">函數的傳回值</a>。 </p><p style="text-align: left;">
接下來可以寫個簡單的測試函數,來比較兩者的運行時間。 </p><pre class="brush:php;toolbar:false">// 定义一个测试函数,将待测函数作为参数传入
function test(func,n){
  let start = new Date().getTime();//起始时间
  let res = func(n);//执行待测函数
  document.write('<br>'+'当n='+n+'的时候 '+res+'<br>');
  let end = new Date().getTime();//结束时间
  return (end - start)+"ms";//返回函数执行需要时间
}

列印函數執行

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

結果如下:

# JS動態規劃使用詳解

# 最後, 你或許已經意識到在使用迭代的方案計算斐波那契數列時, 是可以不使用數組的。

需要用到陣列的原因是因為動態規劃演算法通常需要保存中間結果。

以下是迭代版本的斐波那契函數義

function iterFib(n) {
  let last = 1;
  let nextLast = 1;
  let result = 1;
  for (let i = 2; i <p style="text-align: left;">
當然這個迭代版本的與陣列的版本的效率也是相同的。 </p><p>相信看了本文案例你已經掌握了方法,更多精彩請關注php中文網其它相關文章! </p><p>推薦閱讀:</p><p><a href="http://www.php.cn/js-tutorial-392657.html" target="_blank">Angular4輸入與輸出怎麼使用</a><br></p><p><a href="http://www.php.cn/js-tutorial-392661.html" target="_blank">Vue2.0怎麼操作使用者權限</a><br></p><p style="text-align: left;">
</p><!--content end-->

以上是JS動態規劃使用詳解的詳細內容。更多資訊請關注PHP中文網其他相關文章!

陳述:
本文內容由網友自願投稿,版權歸原作者所有。本站不承擔相應的法律責任。如發現涉嫌抄襲或侵權的內容,請聯絡admin@php.cn