[理工] 幾題時間複雜度計算

[zelkova (*〞︶〝*)]

Q: T(n)=T(n-1)+T(n-2)
A:
   請問這個遞迴不是 a^2-a-1=0，兩解應該是 (1+√5)/2 跟 (1-√5)/2 沒錯吧
   為什麼答案是 O(2^n)？

謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 218.161.45.91
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1487047667.A.7FC.html
※ 編輯: zelkova (218.161.45.91), 02/14/2017 13:08:59
推 weilun911: 用離散的方法可以得出和原po一樣的答案 即為Fn
推 Huffman: 令T(0)=0 T(1)=1
→ Huffman: T(n)=1/√5((1+√5)/2)^n-1/√5((1-√5)/2)^n
推 weilun911: O(2^n)的想法我是覺得
→ weilun911: 約莫為（1.xxx）^n
→ weilun911: 取big O之後是O(2^n)
→ Huffman: 接近O(((1+√5)/2)^n)
推 joejoejoe: (alpha)^n 約等於2^n 前者較精準