作者avogau ( 假 装)
看板TransCSI
标题Re: [问题] 时间复杂度问题
时间Tue Jun 16 18:25:09 2009
※ 引述《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
1F：推 fzrmitsul:谢谢a大^^ 06/20 23:53