[問題] 請問資料結構 Fib 費氏數

[numb4ujb (捲毛)]

我想請問

費氏數 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
→ rockpaulroll:用T(n)=T(n-1)+T(n-2)+1求時間複雜度吧
→ rockpaulroll:阿錯了 不好意思  沒有加1
→ rockpaulroll:特徵解:α^2-α+1=0
推 lh132:用離散方式解遞迴=>O((1+sqrt(5)/2)^n)
推 Sucker:似乎是用特性方程式解出來那條= =
→ numb4ujb:感謝解答~  好像有+1耶  是嗎 因為非遞迴的執行次數@@?
→ rockpaulroll:沒有加1的原因是因為一直Recursive下去而沒有做別的
→ rockpaulroll:運算