第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

為了賬號(hào)安全，請(qǐng)及時(shí)綁定郵箱和手機(jī)立即綁定
已解決430363個(gè)問題，去搜搜看，總會(huì)有你想問的

Fibonacci序列的計(jì)算復(fù)雜性

Fibonacci序列的計(jì)算復(fù)雜性

Fibonacci序列的計(jì)算復(fù)雜性我理解大O表示法，但我不知道如何為許多函數(shù)計(jì)算它。特別是，我一直試圖找出Fibonacci序列的簡(jiǎn)單版本的計(jì)算復(fù)雜性：int Fibonacci(int n) {     if (n <= 1)         return n;     else         return Fibonacci(n - 1) + Fibonacci(n - 2); }斐波納契序列的計(jì)算復(fù)雜度是多少？它是如何計(jì)算的？
查看完整描述

3 回答

?
紅糖糍粑

TA貢獻(xiàn)1815條經(jīng)驗(yàn) 獲得超6個(gè)贊

您可以對(duì)時(shí)間函數(shù)進(jìn)行建模以進(jìn)行計(jì)算。Fib(n)作為計(jì)算的時(shí)間之和Fib(n-1)加上計(jì)算時(shí)間Fib(n-2)加上把它們加在一起的時(shí)間(O(1))。這是假設(shè)重復(fù)評(píng)估相同的Fib(n)采取同樣的時(shí)間-即沒有回憶錄是有用的。

T(n<=1) = O(1)

T(n) = T(n-1) + T(n-2) + O(1)

解決這個(gè)遞歸關(guān)系(例如，使用生成函數(shù))，最終得到答案。

或者，您可以繪制遞歸樹，它將具有深度。n并直觀地計(jì)算出該函數(shù)是漸近的。O(2n)..然后你可以通過歸納來證明你的猜想。

基地：n = 1很明顯

假設(shè)T(n-1) = O(2n-1), 因此

T(n) = T(n-1) + T(n-2) + O(1) 等于

T(n) = O(2n-1) + O(2n-2) + O(1) = O(2n)

然而，正如在評(píng)論中所指出的，這并不是嚴(yán)格的限制。關(guān)于這個(gè)函數(shù)的一個(gè)有趣的事實(shí)是，T(N)是漸近的。同作為.的價(jià)值Fib(n)因?yàn)閮烧叨急欢x為

f(n) = f(n-1) + f(n-2).

遞歸樹的葉子將始終返回1。價(jià)值Fib(n)遞歸樹中葉子返回的所有值之和，等于葉數(shù)。因?yàn)槊科~子都需要O(1)來計(jì)算，T(n)等于Fib(n) x O(1)..因此，這個(gè)函數(shù)的緊界是Fibonacci序列本身(~)θ(1.6n))。您可以像我前面提到的那樣，通過使用生成函數(shù)來找出這種緊密的界限。


查看完整回答
反對(duì) 回復(fù) 2019-06-06
?
拉風(fēng)的咖菲貓

TA貢獻(xiàn)1995條經(jīng)驗(yàn) 獲得超2個(gè)贊

只需問自己需要執(zhí)行多少個(gè)語句就可以了。F(n)完成。

為F(1)，答案是1(條件的第一部分)。

為F(n)，答案是F(n-1) + F(n-2).

那么滿足這些規(guī)則的函數(shù)是什么呢？試一試n(a>1)：

an=a(n-1)+a(n-2)

除以.(n-2):

a2=a+1

解為a你會(huì)得到(1+sqrt(5))/2 = 1.6180339887，也稱為黃金比率.

所以它需要指數(shù)時(shí)間。


查看完整回答
反對(duì) 回復(fù) 2019-06-06
  • 3 回答
  • 0 關(guān)注
  • 705 瀏覽

添加回答

舉報(bào)

0/150
提交
取消
微信客服

購課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

 公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)