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

為了賬號安全，請及時綁定郵箱和手機立即綁定
已解決430363個問題，去搜搜看，總會有你想問的

Fibonacci序列的計算復雜性

Fibonacci序列的計算復雜性

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

3 回答

?
紅糖糍粑

TA貢獻1815條經(jīng)驗 獲得超6個贊

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

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

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

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

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

基地：n = 1很明顯

假設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)

然而，正如在評論中所指出的，這并不是嚴格的限制。關于這個函數(shù)的一個有趣的事實是，T(N)是漸近的。同作為.的價值Fib(n)因為兩者都被定義為

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

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


查看完整回答
反對 回復 2019-06-06
?
拉風的咖菲貓

TA貢獻1995條經(jīng)驗 獲得超2個贊

只需問自己需要執(zhí)行多少個語句就可以了。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你會得到(1+sqrt(5))/2 = 1.6180339887，也稱為黃金比率.

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


查看完整回答
反對 回復 2019-06-06
  • 3 回答
  • 0 關注
  • 690 瀏覽
慕課專欄
更多

添加回答

舉報

0/150
提交
取消
微信客服

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

 幫助反饋 APP下載

慕課網(wǎng)APP
您的移動學習伙伴

 公眾號

掃描二維碼
關注慕課網(wǎng)微信公眾號