成人无码视频,亚洲精品久久久久av无码,午夜精品久久久久久毛片,亚洲 中文字幕 日韩 无码

資訊專欄INFORMATION COLUMN

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

charles_paul / 2779人閱讀

摘要：大名鼎鼎的斐波那契數(shù)列，，，，，，，，使用數(shù)學(xué)歸納法可以看出其規(guī)律為。對于斐波那契數(shù)列的求解，有自頂向下的記憶化搜索遞歸和自下向上的迭代法，他們都使用了動態(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實現(xiàn)）來求解第 n 項：f(n)

// 直接使用遞歸
let num = 0;    // 用來記錄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ù)以及運算總共耗時，結(jié)果如下：

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

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

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

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

// 記憶化搜索，記錄每次計算的結(jié)果
let num = 0; // 用來記錄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)。這其實就是動態(tài)規(guī)劃的思想。什么是動態(tài)規(guī)劃？

Dynamic programming is when you use past knowledge to make solving a future problem easier.(動態(tài)規(guī)劃是用已知項去更好的求解未知項)
Dynamic programming is a technique used to avoid computing multiple time the same subproblem in a recursive algorithm.
將原問題拆解成若干子問題，同時保存子問題的答案，使得每個子問題只求解一次，最終獲得原問題的答案。

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

迭代法(自下向上)

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

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é)

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

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

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://m.hztianpu.com/yun/95942.html

相關(guān)文章

  • 時間復(fù)雜度、遞歸、尾調(diào)用— (讀文筆記)

    摘要：遞歸算法是一種直接或者間接調(diào)用自身函數(shù)或者方法的算法。因此，分治策略一般用來解決子問題相互對立的問題，稱為標(biāo)準(zhǔn)分治，而動態(tài)規(guī)劃用來解決子問題重疊的問題。調(diào)用棧尾遞歸和手動優(yōu)化尾調(diào)用就是一個函數(shù)執(zhí)行的最后一步是將另外一個函數(shù)調(diào)用并返回。 輸出 斐波那契數(shù)列的四種寫法 讀參考文章列表 算法復(fù)雜度中的O(logN)底數(shù)是多少 從斐波那契數(shù)列談?wù)劥a的性能優(yōu)化 冰與火之歌：時間與空間復(fù)雜度 ...

    susheng 評論0 收藏0

  • js 實現(xiàn)斐波那契數(shù)列(數(shù)組緩存、動態(tài)規(guī)劃、尾調(diào)用優(yōu)化)

    摘要：根據(jù)該規(guī)則，返回第個斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個前端眼中的斐波那契數(shù)列解斐波那契數(shù)列的實用解法調(diào)用棧尾遞歸和手動優(yōu)化尾調(diào)用優(yōu)化譯我從用寫斐波那契生成器中學(xué)到的令人驚訝的件事 斐波那契數(shù)列是以下一系列數(shù)字： 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數(shù)字 0 和 1 ...

    趙連江 評論0 收藏0

  • 動態(tài)規(guī)劃問題（1）——斐波那契數(shù)列

    摘要：動態(tài)規(guī)劃有時被稱為遞歸的相反的技術(shù)。動態(tài)規(guī)劃方案通常使用一個數(shù)組來建立一張表，用于存放被分解成眾多子問題的解。今天我們先從我們最熟的斐波那契數(shù)列數(shù)列開始。斐波那契數(shù)列在很多地方都會用上，我是從一個臺階問題發(fā)現(xiàn)的，同時知道了動態(tài)規(guī)劃的解法。 前段時間一直寫了幾個算法題目，發(fā)現(xiàn)有個很牛逼的算法，動態(tài)規(guī)劃，雖然有的解題思路和動態(tài)規(guī)劃很像，但是當(dāng)時不知道其中的原理和一些通用性，接下來的幾天，通...

    Eminjannn 評論0 收藏0

  • 斐波那契數(shù)列求和的js方案以及優(yōu)化

    摘要：在上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實現(xiàn)。動態(tài)規(guī)劃解決方案斐波那契數(shù)列求和除了可以用遞歸的方法解決，還可以用動態(tài)規(guī)劃的方法解決。 在codewars上做了一道斐波那契數(shù)列求和的題目，做完之后做了一些簡單的優(yōu)化和用另一種方法實現(xiàn)。 題目 function fibonacci(n) { if(n==0 || n == 1) r...

    xinhaip 評論0 收藏0

  • 數(shù)據(jù)結(jié)構(gòu)與算法:常見排序算法

    摘要：這是一個簡單的遞歸函數(shù)，你可以使用它來生成數(shù)列中指定序號的數(shù)值這個函數(shù)的問題在于它的執(zhí)行效率非常低有太多值在遞歸調(diào)用中被重新計算。 本章內(nèi)容銜接上一章　數(shù)據(jù)結(jié)構(gòu)與算法：二分查找 內(nèi)容提要 兩種基本數(shù)據(jù)結(jié)構(gòu)： 數(shù)組 常見操作: 數(shù)組降維、數(shù)組去重 鏈表 遞歸：遞歸是很多算法都使用的一種編程方法 　　- 如何將問題分成基線條件和遞歸條件 　　- 分而治之策略解決棘手問題 ...

    wuyumin 評論0 收藏0

發(fā)表評論

0條評論

閱讀需要支付1元查看
<