【刷算法】斐波那契數(shù)列

IamDLY 發(fā)布于2019-08-22 18:09 / 635人閱讀

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

題目

現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第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)太高，而且用遞歸會產(chǎ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個數(shù)時，使用了s1、s2兩個變量存儲第n-1和第n-2個數(shù)，使時間復雜度降低到O(n)

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

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

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

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

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

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

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

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

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

Galence 2019-08-26 12:01 評論0 收藏0
動態(tài)規(guī)劃問題（1）——斐波那契數(shù)列

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

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

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

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