摘要:轉載自我的博客效率呢斐波那契數列大家應該再熟悉不過了,平時面試也經常會被問到,然而不知道大家有沒有考慮過它的效率呢普通版我們一般給出的代碼應該是這樣的這段代碼邏輯完全沒問題,但是如果你稍測試一下可能就會發現問題了,比如可以試一下,這時你
效率呢?轉載自 我的博客
斐波那契數列大家應該再熟悉不過了,平時面試也經常會被問到,然而不知道大家有沒有考慮過它的效率呢?
普通版我們一般給出的代碼應該是這樣的:
function fibonacci(n) { if(n==0 || n == 1) return n; return fibonacci(n-1) + fibonacci(n-2); }
這段代碼邏輯完全沒問題,但是如果你稍測試一下可能就會發現問題了,比如可以試一下 fibonacci(70),這時你可能吃個飯回來它還沒執行完。
{{BANNED}}版之所以叫它“{{BANNED}}版”,是因為在fibonacci(1000)以下基本可以在 5 毫秒之內完成,效率提升了 Infinity 倍,然而為什么差距這么大?我們先看個圖:
這是n = 5的時候的計算過程,顯而易見,它包含了很多次重復的計算,優化它也很簡單,我們只需要加個緩存(這里用到了閉包),代碼如下:
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; } })()
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/80954.html
摘要:很好地遇到了斐波那契更大的兄弟,。它基本上像斐波納契一樣,但是將序列的最后個而不是個數相加以生成下一個。入參的數組始終包含個數字將始終為非負數,然后返回一個空數組。同時需要注意的的情況。 很好地遇到了斐波那契更大的兄弟,AKA Tribonacci。 它基本上像斐波納契一樣,但是將序列的最后3個(而不是2個)數相加以生成下一個。 所以,如果我們要以開始[1, 1, 1]輸入開始我們...
摘要:根據該規則,返回第個斐波那契數。尾遞歸函數調用自身,稱為遞歸。一個前端眼中的斐波那契數列解斐波那契數列的實用解法調用棧尾遞歸和手動優化尾調用優化譯我從用寫斐波那契生成器中學到的令人驚訝的件事 斐波那契數列是以下一系列數字: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, ... 在種子數字 0 和 1 ...
摘要:在上做了一道斐波那契數列求和的題目,做完之后做了一些簡單的優化和用另一種方法實現。動態規劃解決方案斐波那契數列求和除了可以用遞歸的方法解決,還可以用動態規劃的方法解決。 在codewars上做了一道斐波那契數列求和的題目,做完之后做了一些簡單的優化和用另一種方法實現。 題目 function fibonacci(n) { if(n==0 || n == 1) r...
摘要:那其實這個問題還可以換個問法實現一個函數,輸入一個數字能返回斐波那契數列的第個值。文章預告更多的前端面試分享我都會第一時間更新在我的公眾號閏土大叔里面,歡迎關注 面試攢經驗,lets go! 值此高考來臨之際,閑不住的我又雙叒叕出發去面試攢經驗了,去了公司交待一番流程后,面試官甩給了我一張A4紙,上面寫著一道js算法筆試題(一開始我并不知道這是在考察js算法),上面寫著1、1、2、3、...
摘要:實現斐波那契數列斐波那契數列最大數斐波那契數列由和開始之后的斐波那契數列系數就由之前的兩數相加。換個寫法,用箭頭函數最大數斐波那契數列由和開始 js實現斐波那契數列 // 斐波那契數列 let max=10000; // 最大數 let arr=[0,1]; // 斐波那契數列由 0 和 1 開始 // 之后的斐波那契數列系數就由之前的兩數相加。 ...
閱讀 3159·2021-10-14 09:42
閱讀 3564·2019-08-26 13:56
閱讀 3446·2019-08-26 11:59
閱讀 938·2019-08-23 18:00
閱讀 2197·2019-08-23 17:51
閱讀 3522·2019-08-23 17:17
閱讀 1479·2019-08-23 15:11
閱讀 5146·2019-08-23 15:05