【JS 小短文】{{BANNED}}版斐波那契

sihai 發(fā)布于2019-08-20 12:23 / 2718人閱讀

摘要：轉(zhuǎn)載自我的博客效率呢斐波那契數(shù)列大家應(yīng)該再熟悉不過了，平時面試也經(jīng)常會被問到，然而不知道大家有沒有考慮過它的效率呢普通版我們一般給出的代碼應(yīng)該是這樣的這段代碼邏輯完全沒問題，但是如果你稍測試一下可能就會發(fā)現(xiàn)問題了，比如可以試一下，這時你

轉(zhuǎn)載自 我的博客

效率呢？

斐波那契數(shù)列大家應(yīng)該再熟悉不過了，平時面試也經(jīng)常會被問到，然而不知道大家有沒有考慮過它的效率呢？

普通版

我們一般給出的代碼應(yīng)該是這樣的：

function fibonacci(n) {
    if(n==0 || n == 1)
        return n;
    return fibonacci(n-1) + fibonacci(n-2);
}

這段代碼邏輯完全沒問題，但是如果你稍測試一下可能就會發(fā)現(xiàn)問題了，比如可以試一下 fibonacci(70)，這時你可能吃個飯回來它還沒執(zhí)行完。

{{BANNED}}版

之所以叫它“{{BANNED}}版”，是因為在fibonacci(1000)以下基本可以在 5 毫秒之內(nèi)完成，效率提升了 Infinity 倍，然而為什么差距這么大？我們先看個圖：

這是n = 5的時候的計算過程，顯而易見，它包含了很多次重復(fù)的計算，優(yōu)化它也很簡單，我們只需要加個緩存（這里用到了閉包），代碼如下：

var fibonacci = (function() {
  // 這里我用了 Map，用普通對象也是可以的
  var cache = new Map();
   return function(n){
       if(n == 0 || n == 1){
       cache.set(n,n);
       return n;
      }
      var v1 = cache.get(n-1) ? cache.get(n-1):fibonacci(n-1);
      var v2 = cache.get(n-2) ? cache.get(n-2):fibonacci(n-2);
      var nVal = v1 + v2;
      cache.set(n, nVal);
      return nVal;
   }
})()

GPU云服務(wù)器云服務(wù)器波那契數(shù)列解斐波短文 js小技能

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

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/80954.html

相關(guān)文章

增強(qiáng)版斐波納契函數(shù)Tribonacci

摘要：很好地遇到了斐波那契更大的兄弟，。它基本上像斐波納契一樣，但是將序列的最后個而不是個數(shù)相加以生成下一個。入?yún)⒌臄?shù)組始終包含個數(shù)字將始終為非負(fù)數(shù)，然后返回一個空數(shù)組。同時需要注意的的情況。很好地遇到了斐波那契更大的兄弟，AKA Tribonacci。它基本上像斐波納契一樣，但是將序列的最后3個（而不是2個）數(shù)相加以生成下一個。所以，如果我們要以開始[1, 1, 1]輸入開始我們...

JellyBool 2019-08-16 16:22 評論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 ...

趙連江 2019-08-23 11:38 評論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 2019-08-20 11:35 評論0 收藏0
太原面經(jīng)分享：如何用js實現(xiàn)返回斐波那契數(shù)列的第n個值的函數(shù)

摘要：那其實這個問題還可以換個問法實現(xiàn)一個函數(shù)，輸入一個數(shù)字能返回斐波那契數(shù)列的第個值。文章預(yù)告更多的前端面試分享我都會第一時間更新在我的公眾號閏土大叔里面，歡迎關(guān)注面試攢經(jīng)驗，lets go！值此高考來臨之際，閑不住的我又雙叒叕出發(fā)去面試攢經(jīng)驗了，去了公司交待一番流程后，面試官甩給了我一張A4紙，上面寫著一道js算法筆試題（一開始我并不知道這是在考察js算法），上面寫著1、1、2、3、...

Galence 2019-08-26 12:01 評論0 收藏0
js實現(xiàn)斐波那契數(shù)列

摘要：實現(xiàn)斐波那契數(shù)列斐波那契數(shù)列最大數(shù)斐波那契數(shù)列由和開始之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加。換個寫法，用箭頭函數(shù)最大數(shù)斐波那契數(shù)列由和開始 js實現(xiàn)斐波那契數(shù)列 // 斐波那契數(shù)列 let max=10000; // 最大數(shù) let arr=[0,1]; // 斐波那契數(shù)列由 0 和 1 開始 // 之后的斐波那契數(shù)列系數(shù)就由之前的兩數(shù)相加。 ...

notebin 2019-08-23 15:42 評論0 收藏0