作者numb4ujb (捲毛)
看板Grad-ProbAsk
標題[問題] 請問資料結構 Fib 費氏數
時間Thu Mar 19 17:48:59 2009
我想請問
費氏數 fib 的時間複雜度是多少呢!!?
void Fib(int n)
{
if (n <= 1)
return n;
else
return (Fib(n-1) + Fib(n-2));
}
腦筋突然轉不過來 ..
希望能附上算式 感謝 ><
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 218.165.195.215
1F：→ rockpaulroll:用T(n)=T(n-1)+T(n-2)+1求時間複雜度吧 03/19 17:53
2F：→ rockpaulroll:阿錯了 不好意思 沒有加1 03/19 17:53
3F：→ rockpaulroll:特徵解:α^2-α+1=0 03/19 17:56
4F：推 lh132:用離散方式解遞迴=>O((1+sqrt(5)/2)^n) 03/19 17:57
5F：推 Sucker:似乎是用特性方程式解出來那條= = 03/19 17:57
6F：→ numb4ujb:感謝解答~ 好像有+1耶 是嗎 因為非遞迴的執行次數@@? 03/19 17:58
7F：→ rockpaulroll:沒有加1的原因是因為一直Recursive下去而沒有做別的 03/19 18:01
8F：→ rockpaulroll:運算 03/19 18:01