阿摩線上測驗
登入
阿摩線上測驗
登入
三、斐波那契數（Fibonacci number）Fn的定義為：F0 = 0, F1 = 1, Fn= Fn-1 + Fn-2 ,n ＞ 1。下面是一個計算斐波那契數 Fn 的演算法，以類似 C 語言的函數（C function）表示，其中資料型態 integer 表示整數。 
假設輸入的整數 n≧0。證明此程式的計算複雜度 T(n) ＞ Fn。在分析計算複雜度時，可將“==”, “=”, “+”和“return”當作只需要一個單位時間的運算。（25 分）