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

看板Grad-ProbAsk作者 (捲毛)時間17年前 (2009/03/19 17:49), 編輯推噓2(2推 0噓 6→)
留言8則, 4人參與, 最新討論串1/1
我想請問 費氏數 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
→
03/19 17:53, , 1F
用T(n)=T(n-1)+T(n-2)+1求時間複雜度吧
03/19 17:53, 1F
→
03/19 17:53, , 2F
阿錯了 不好意思 沒有加1
03/19 17:53, 2F
→
03/19 17:56, , 3F
特徵解:α^2-α+1=0
03/19 17:56, 3F
推
03/19 17:57, , 4F
用離散方式解遞迴=>O((1+sqrt(5)/2)^n)
03/19 17:57, 4F
推
03/19 17:57, , 5F
似乎是用特性方程式解出來那條= =
03/19 17:57, 5F
→
03/19 17:58, , 6F
感謝解答~ 好像有+1耶 是嗎 因為非遞迴的執行次數@@?
03/19 17:58, 6F
→
03/19 18:01, , 7F
沒有加1的原因是因為一直Recursive下去而沒有做別的
03/19 18:01, 7F
→
03/19 18:01, , 8F
運算
03/19 18:01, 8F
‣ 更多 numb4ujb 的文章
文章代碼(AID): #19mXKCjb (Grad-ProbAsk)