當前位置:首頁 » 操作系統 » 斐波那契數列的遞歸演算法

斐波那契數列的遞歸演算法

發布時間: 2024-05-04 14:34:55

⑴ [數據結構與演算法分析]斐波那契數列遞歸演算法時間復雜度為多少

longfab(longn)
{
if(n<2)return1;
returnfab(n-1)+fab(n-2);
}

簡單推斷一下,當n>2時,遞歸調用的次數call_fab(n) = 2*fab(n) - 1,再簡單證明一下。

用call_fab(n)代表遞歸調用的次數

n = 3時,調用fab(3),會遞歸調用fab(1)和fab(2),而fab(1)和fab(2)只需要調用一次,加上本身一次,一共調用3次,而fab(3) = 2,3 = 2 * 2 - 1,滿足推斷

n = 4時,fab(4) = fab(3) + fab(2),所以call_fab(4) = 1 + call_fab(3) + call_fab(2) = 5

fab(4) = 3,滿足5 = 3 * 2 - 1

同理n=5也可以簡單計算得出,這樣我有連續3個結果,作為歸納法證明的基礎

假設n = k(k >= 5)成立,即

fab(k) = fab(k-2) + fab(k - 1),有call_fab(k) = 2fab(k) - 1

那麼當n=k+1時,fab(k+1) = fab(k - 1) + fab(k),

call_fab(k+1) = 1 + call_fab(k - 1) + call_fab(k) = 1 + 2fab(k-1) - 1 + 2fab(k) - 1

= 2(fab(k-1) + fab(k)) - 1 = 2fab(k+1) - 1,歸納法得證。

所以,對於大於2的整數n,其斐波那契數列遞歸演算法的調用次數為2*n的斐波那契數列值 - 1,故答案是D,時間復雜度和該數列是一致的。

熱點內容
低能耗電腦列印伺服器 發布:2025-03-09 10:45:06 瀏覽:313
英雄聯盟免費腳本 發布:2025-03-09 10:38:14 瀏覽:26
簡訊報警腳本 發布:2025-03-09 10:27:54 瀏覽:953
寫腳本的大嬸 發布:2025-03-09 10:19:27 瀏覽:629
安卓app怎麼上線 發布:2025-03-09 10:15:11 瀏覽:149
pythonlistmax 發布:2025-03-09 10:15:10 瀏覽:681
c語言排班 發布:2025-03-09 10:06:48 瀏覽:278
安卓手機網路通訊出現問題怎麼辦 發布:2025-03-09 10:02:05 瀏覽:288
華為nm存儲卡軟體未響應 發布:2025-03-09 09:57:44 瀏覽:610
問你個密碼是多少 發布:2025-03-09 09:56:05 瀏覽:870