推 fzrmitsul:謝謝a大^^ 06/20 23:53
※ 引述《fzrmitsul (我的妹妹很可愛)》之銘言：
: Fun(n:integer)
: begin
: if (n=0 or 1) then
: Fun=1
: else
: Fun=Fun(n-1)+Fun(n-2)
: end.
: 請問時間複雜度為何?
: (a)O(nlogn) (b)O(n^2) (c)O(2^n) (d)O(n!)
: 對於這一類的題目，小弟實在不知該怎麼判別。
: 可否請教前輩能指導。謝謝
因為 要算 Fn 時 必須分別先算 Fn-1 , Fn-2
令 計算 Fn 的時間為 T(n)
=> T(n) = T(n-1) + T(n-2) , T(0)=T(1) = O(1)
接下來 利用離散數學所學的解遞迴的方式
可以解出T(n) (數字很複雜)
所以複雜度大約為
(√5)+1 ^N
[ ---------- ]
2
所以是 (c)O(2^n)
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.45.50.20