→ taitin:法2，法一不夠tught 看結果就知道 02/24 22:59
→ taitin: tight 02/24 22:59
→ polomoss:法一是哪招~還可以這樣合喔~~" 02/24 23:28
→ hungyanbin:第三行3*(n-2)是沒打完整嗎.....? 02/24 23:34
推 hoverg:我也想知道…法一是怎麼合的…？？？ 02/25 00:40
int fib(int n){
if (n==0 || n==1) return 100;
else return 2*fib(n-1)+3*(n-2); }
我有兩種想法來解，不知道哪一種是對的
請大家幫我看看
(1) t(n)= t(n-1)+t(n-2)+1 <= 2*t(n-1)+1
= 2^2*t(n-2)+2^2-1
= ............
= 2^(n-1)*t(n-(n-1))+2^(n-1)-1
= 2^(n-1)*t(1)+2^(n-1)-1
= 2^n-1
= O(2^n)
(2)t(n)= t(n-1)+t(n-2)
= x1((1+√5)/2)^n + x2((1-√5)/2)^n
x1= 1/√5 , x2= - 1/√5
t(n) = O(((1+√5)/2)^n)
用離散去解
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.47.237.29