測驗達人

susan
博一上
54270次
司法特考錄..
高二下
53569次
魯筱筱
研二下
44648次
Cyril..
研二上
38321次
錄事考試
小六下
25910次

教甄◆電腦科專業題庫

【非選題】8.請以演算法語法或C 語言寫出費氏數列(Fibonacci)的遞迴演算法和非遞迴演算法,並寫出這 兩種演算法的Big O值。(6 分)

#12776
編輯私有筆記
1F
彤媽 (2014/07/15 16:36):
費氏陣列的解法很多,基本上可以使用遞迴解,演算法最簡單,如下: 
Procedure FIB(N)
IF (N = 0 OR N = 1)
RETURN N
ELSE
RETURN FIB(N-1) + FIB(N-2)


簡單,但是不實用,因為太慢了,在求每一個費氏數時,都會發生嚴重的重覆計算,也就是遞迴該行 ( FIB(N-1) + FIB(N-2) ),最差的big-o可以到2的n/2次方,畫張遞迴的樹狀圖就可以知道重覆計算的數有多少了。 

可以採取非遞迴的版本,可以將big(o)減至n,演算法如下: 
Procedure FIB(N)
IF (N = 0 OR N = 1)
RETURN N

a = 0;
b = 1;
FOR i = 2 TO N [
temp = b;
b = a + b;
a = temp;
]
RETURN b;
]