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

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

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

題目

現(xiàn)在要求輸入一個(gè)整數(shù)n，請(qǐng)你輸出斐波那契數(shù)列的第n項(xiàng)。

遞歸操作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);
}

時(shí)間復(fù)雜度O(2^n)太高，而且用遞歸會(huì)產(chǎn)生很多重復(fù)的操作。

非遞歸操作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;
}

這種方法就是一次遍歷過(guò)去就行，計(jì)算第n個(gè)數(shù)時(shí)，使用了s1、s2兩個(gè)變量存儲(chǔ)第n-1和第n-2個(gè)數(shù)，使時(shí)間復(fù)雜度降低到O(n)

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

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

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

相關(guān)文章

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

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

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

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

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

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

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

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

Eminjannn 2019-08-21 11:24 評(píng)論0 收藏0
數(shù)據(jù)結(jié)構(gòu)與算法:常見(jiàn)排序算法

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

wuyumin 2019-07-30 15:33 評(píng)論0 收藏0