【刷算法】斐波那契數列

IamDLY 發布于2019-08-22 18:09 / 637人閱讀

摘要：題目現在要求輸入一個整數，請你輸出斐波那契數列的第項。遞歸操作時間復雜度太高，而且用遞歸會產生很多重復的操作。非遞歸操作這種方法就是一次遍歷過去就行，計算第個數時，使用了兩個變量存儲第和第個數，使時間復雜度降低到

題目

現在要求輸入一個整數n，請你輸出斐波那契數列的第n項。

遞歸操作O(2^n)

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

時間復雜度O(2^n)太高，而且用遞歸會產生很多重復的操作。

非遞歸操作O(n)

function Fibonacci(n)
{
    if(n < 1)
        return 0;
    if(n === 1 || n === 2)
        return 1;
    var s1 = 1;
    var s2 = 1;
    var res = 0;
    for(var  i = 3;i <= n;i++) {
        res =  s1 + s2;
        s1 = s2;
        s2 = res;
    }
    
    return res;
}

這種方法就是一次遍歷過去就行，計算第n個數時，使用了s1、s2兩個變量存儲第n-1和第n-2個數，使時間復雜度降低到O(n)

云服務器 GPU云服務器波那契數列算法最大子數列解斐波遞減數列

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/95551.html

【刷算法】我知道的所有類似斐波那契數列的問題

摘要：有一類算法問題類似斐波那契數列，而且解決辦法基本差不多。不了解斐波那契套路的可以看刷算法斐波那契數列跳臺階問題題目描述一只青蛙一次可以跳上級臺階，也可以跳上級。給定整數，求年后牛的數量。分析設為年后牛的數量，則第年牛的來源有兩個。有一類算法問題類似斐波那契數列，而且解決辦法基本差不多。不了解斐波那契套路的可以看【刷算法】斐波那契數列跳臺階問題題目描述一只青蛙一次可以跳上1級臺階，...

NotFound 2019-08-22 18:10 評論0 收藏0
算法記錄 >> 斐波那契數列

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

robin 2019-08-16 17:52 評論0 收藏0
太原面經分享：如何用js實現返回斐波那契數列的第n個值的函數

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

Galence 2019-08-26 12:01 評論0 收藏0
動態規劃問題（1）——斐波那契數列

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

Eminjannn 2019-08-21 11:24 評論0 收藏0
數據結構與算法:常見排序算法

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

wuyumin 2019-07-30 15:33 評論0 收藏0