教甄◆電腦科專業題庫

【非選題】
8.請以演算法語法或C 語言寫出費氏數列(Fibonacci)的遞迴演算法和非遞迴演算法,並寫出這 兩種演算法的Big O值。(6 分)
編輯私有筆記及自訂標籤
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;
]