阿摩線上測驗
9 費氏數列（Fibonacci number）之定義如下：
假設 n0=0，n1=1，則 n2 = n1+n0=1+0=1，n3 = n2+n1=1+1=2，…，ni = ni-1+ni-2
若以遞迴法撰寫程式計算費氏數列，給定一個 n 值，求解費氏數列第 n 項的值，請問時間複雜度為何？
(A) O(n)
(B) O(n2 )
(C) O(n log n)
(D) O(2n )
答案：登入後查看
統計： A(94), B(145), C(192), D(194), E(0) #798374
統計： A(94), B(145), C(192), D(194), E(0) #798374
詳解 (共 5 筆)
AT
#1303077
時間複雜度可以說成是「動作做幾次」
以這個題目來說，費氏數列的遞迴寫法會是 :
int F(int n)
{
if(n<=2) return 1;
return F(n-1)+F(n-2);
}
解開來看就不難理解，最後他會變成2^n
example:
F(8)
= F(7)+F(6)
= F(6)+F(5)+F(5)+F(4)
= F(5)+F(4)+F(4)+F(3)+F(4)+F(3)+F(3)+F(2)
展開3層就變成 8 （=2^3）個 F(n)的樣子了
以此類推
33
0
AT
#1162633
遞迴的複雜度 O(2^n) ，但迴圈複雜度只要 O(n)
以費氏數列這個程式來看，以這兩種方法來寫，都相當的簡單，好懂，但是以程式執行時，所佔的資源與所花費的時間來看，遞迴需花費相當大的 Stack 空間，來儲存每個節點（function call ）， 因為每個節點無法共用空間，若 N 的值相當大，那麼程式執行時就得花費相當大的空間與時間 。而 For loop 程式執行時所花的時間與空間都相對於遞迴都少了許多。
http://sun.cis.scu.edu.tw/~90a50/My%20Webs/right-4.htm
7
0
Adam Lin
#1302025
想問遞迴的複雜度怎麼判斷的?
迴圈比較好理解
迴圈比較好理解
2
0
