[理工] [資結]-時間複雜度
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
→
02/24 22:59, , 1F
02/24 22:59, 1F
→
02/24 22:59, , 2F
02/24 22:59, 2F
→
02/24 23:28, , 3F
02/24 23:28, 3F
→
02/24 23:34, , 4F
02/24 23:34, 4F
推
02/25 00:40, , 5F
02/25 00:40, 5F
討論串 (同標題文章)
完整討論串 (本文為第 32 之 38 篇)：
理工
3
15