成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

JavaScript解斐波那契(Fibonacci)數(shù)列的實(shí)用解法

zhongmeizhi / 1477人閱讀

摘要：下面是一個可以處理很多類型遞歸函數(shù)的函數(shù)其中第一個參數(shù)為原有函數(shù)，第二個參數(shù)為緩存對象，是可選參數(shù)因為并不是所有遞歸函數(shù)都包含初始信息。首先將緩存對象的類型從數(shù)組轉(zhuǎn)換為對象，這樣就可以適用于那些不是返回整數(shù)的遞歸函數(shù)。

JavaScript解斐波那契(Fibonacci)數(shù)列的實(shí)用解法

我們經(jīng)常會在面試題中看到如下題目：輸入n，求斐波那契數(shù)列的第n項，斐波那契數(shù)列的定義如下：

F(0)=0, F(1)=1, n>1時，F(xiàn)(n)=F(n-1)+F(n-2)。

一種效率很低的解法

當(dāng)遇到這種函數(shù)時，我們很容易的想到遞歸函數(shù)，解法如下：

function fibonacci(n) {
  if(n <= 1) {return n};
  else {
    return fibonacci(n-1) + fibonacci(n-2);
  }
}

這個方法確實(shí)能解決這道題目，但遞歸的解法并不適合這道題目，用遞歸解法將會有很嚴(yán)重的效率問題，我們以f(10)為例分析一下原因：

由上述圖片我們可以看出，要想求得f(10),需要先求得f(8)和f(9)，同樣，要想求得f(9)，也要求得f(7)和f(8)。不難看出，樹結(jié)構(gòu)當(dāng)中很多結(jié)點(diǎn)是重復(fù)的，而且重復(fù)的節(jié)點(diǎn)數(shù)會隨著n的增大而急劇增大，這意味著計算量將會隨著n的增大而急劇增大。事實(shí)上，遞歸所需的時間復(fù)雜度是以n的指數(shù)方式遞增的，由此我們可以試試當(dāng)n為100時需要耗費(fèi)的時間會有多長，這是難以接受的。

動態(tài)規(guī)劃解法

造成效率低下的主要原因就是重復(fù)計算太多，我們只要想個辦法避免重復(fù)計算即可，這里有個很容易的算法：

var fib = 0,
    fib1 = 0,
    fib2 = 1;
function fibonacci(n) {
  if(n <= 1){
    return n;
  } else {
    for(var i =1; i < n; ++i) {
      fib = fib1 + fib2;
      fib1 = fib2;
      fib2 = fib;
    }
    return fib;
  }
}

理解這種方法很簡單，我們只是從下往上計算，首先根據(jù)f(0)和f(1)算出f(2),再根據(jù)f(1)和f(2)算出f(3)，依次類推我們就可以算出第n項了，而這種算法的時間復(fù)雜度僅為O(n)，比遞歸函數(shù)的寫法效率要大大增強(qiáng)。

Memoization

我們還可以將已經(jīng)得到的數(shù)列中間項保存起來，若下次計算的時候我們先查找一下，若前面已經(jīng)出現(xiàn)過則不用再重復(fù)計算了。

在JavaScript中，遞歸是拖慢腳本運(yùn)行速度的罪魁禍?zhǔn)字?，太多的遞歸會讓瀏覽器越來越慢乃至奔潰，這是需要我們解決的性能問題。

我們可以使用memoization技術(shù)來替代函數(shù)中太多的遞歸調(diào)用，memoization是一種可以緩存之前運(yùn)算結(jié)果的一種技術(shù)，當(dāng)在執(zhí)行運(yùn)算操作時，我們先從緩存對象中讀取看看是否有我們需要讀取的值，若有則直接從緩存對象中讀取，若沒有則進(jìn)行計算，并將緩存結(jié)果存入緩存對象中。

下面是一個可以處理很多類型遞歸函數(shù)的memoizer()函數(shù)：

`function memoizer(fun, cache) {


 cache = cache || {};
 var shell = function(arg) {
   if( ! (arg in cache)) {
     cache[arg] = fun(shell, arg);
   }
   return cache[arg];
 } ;
 return shell;


}`

其中第一個參數(shù)為原有函數(shù)，第二個參數(shù)為緩存對象，是可選參數(shù)（因為并不是所有遞歸函數(shù)都包含初始信息）。首先將緩存對象的類型從數(shù)組轉(zhuǎn)換為對象，這樣就可以適用于那些不是返回整數(shù)的遞歸函數(shù)。使用in操作符判斷參數(shù)是否已經(jīng)包含在了緩存里，會比測試cache[arg]更安全些，因為undefined是一個有效的返回值(這里其實(shí)我也不太明白，弄清楚后會補(bǔ)上)。

接下來我們就可以調(diào)用memoizer來解這個這個問題:

var fibonacci = memoizer(function(fibon, n) {
  return fibon(n - 1) + fibon(n - 2);
}, {"0" : 0, "1" : 1});

這時我們就可以通過fibonacci(100)來執(zhí)行函數(shù)，同樣運(yùn)用此種方法復(fù)雜度為O(n)，大大優(yōu)化了執(zhí)行效率。

后記

個人更喜歡memoizer的解法，因為我覺得這種解法更加的優(yōu)雅，運(yùn)用了JavaScript函數(shù)式編程的特性，非常值得借鑒。

在我看來，函數(shù)的執(zhí)行效率很重要，勿以事小而不為，平時多積累一些優(yōu)秀的解法，從平時的小知識點(diǎn)出發(fā)，慢慢進(jìn)步，假以時日終將也可以寫出優(yōu)雅高效率的方法

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

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

相關(guān)文章

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

    摘要：根據(jù)該規(guī)則，返回第個斐波那契數(shù)。尾遞歸函數(shù)調(diào)用自身，稱為遞歸。一個前端眼中的斐波那契數(shù)列解斐波那契數(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

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

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

    xinhaip 評論0 收藏0

  • 斐波那契數(shù)列（求fibonacci的第N項的值）

    摘要：今天在公司實(shí)習(xí)，實(shí)在沒啥活是我能干的，就想著寫一寫算法打發(fā)時間，正好看到了斐波那契數(shù)列，搞起。這是斐波那契數(shù)列的通項公式以前用遞歸寫過，今天看的時候書上說遞歸雖然簡單，但其實(shí)內(nèi)部做了很多重復(fù)的計算，而且尾遞歸都是可以用循環(huán)解決的。 今天在公司實(shí)習(xí)，實(shí)在沒啥活是我能干的，就想著寫一寫算法打發(fā)時間，正好看到了斐波那契數(shù)列，搞起。 這是斐波那契數(shù)列的通項公式：showImg(https://...

    Fundebug 評論0 收藏0

  • 使用js實(shí)現(xiàn)斐波那契數(shù)列

    摘要：前言前幾天面試被問到了斐波那契數(shù)列的實(shí)現(xiàn)以及優(yōu)化的問題，當(dāng)時現(xiàn)場卡了挺久的，現(xiàn)在進(jìn)行一下總結(jié)使用實(shí)現(xiàn)。題目介紹斐波那契數(shù)列又被稱為黃金分割數(shù)列，指的是這樣的一個數(shù)列，它有如下遞推的方法定義是正整數(shù)，請使用實(shí)現(xiàn)斐波那契函數(shù)。 前言 前幾天面試被問到了斐波那契數(shù)列的實(shí)現(xiàn)以及優(yōu)化的問題，當(dāng)時現(xiàn)場卡了挺久的，現(xiàn)在進(jìn)行一下總結(jié)（使用js實(shí)現(xiàn)）。 題目介紹 ??斐波那契數(shù)列又被稱為黃金分割數(shù)列，指...

    alexnevsky 評論0 收藏0

  • 算法記錄 >> 斐波那契數(shù)列

    摘要：今天去面試筆試題斐波那契數(shù)列實(shí)現(xiàn)，雖然很簡單。回來想想既然算法這么重要那就從這個開始來記錄自己的算法庫吧。在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義，，。斐波拉契算法規(guī)律很簡單，，觀察下數(shù)列值就很容易總結(jié)出來了。 一、寫在前面 算法這塊對于大多數(shù)程序員（包括我）來說可能都是一個薄弱的地方，如何彌補(bǔ)尼？ 每個人都知道那就是學(xué)習(xí)、特別是算法沒有任何捷徑可走。 在這記錄平時自己工作和生...

    robin 評論0 收藏0

發(fā)表評論

0條評論

最新活動
閱讀需要支付1元查看
<