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

看板Grad-ProbAsk作者 (*〞︶〝*)時間8年前 (2017/02/14 12:47), 8年前編輯推噓4(4推 0噓 4→)
留言8則, 3人參與, 最新討論串1/1
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
推
02/14 13:28, , 1F
用離散的方法可以得出和原po一樣的答案 即為Fn
02/14 13:28, 1F
推
02/14 13:30, , 2F
令T(0)=0 T(1)=1
02/14 13:30, 2F
→
02/14 13:31, , 3F
T(n)=1/√5((1+√5)/2)^n-1/√5((1-√5)/2)^n
02/14 13:31, 3F
推
02/14 13:32, , 4F
O(2^n)的想法我是覺得
02/14 13:32, 4F
→
02/14 13:32, , 5F
約莫為（1.xxx）^n
02/14 13:32, 5F
→
02/14 13:32, , 6F
取big O之後是O(2^n)
02/14 13:32, 6F
→
02/14 13:33, , 7F
接近O(((1+√5)/2)^n)
02/14 13:33, 7F
推
02/14 13:53, , 8F
(alpha)^n 約等於2^n 前者較精準
02/14 13:53, 8F
‣ 更多 zelkova 的文章
文章代碼(AID): #1OeelpVy (Grad-ProbAsk)