申論題

費氏陣列的解法很多，基本上可以使用遞迴解，演算法最簡單，如下： 
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;
]