[理工] 資結 複雜度

[gary19941208 ()]

http://i.imgur.com/ap9FhYW.jpg

請問第一小題怎麼算，答案是O(2^n)

我列的時間方程式是T(n)=T(n-1)+T(n-2)+3，3是兩個乘和一個加
不知道有沒有列錯，謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.112.25.105
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1471170366.A.097.html
推 A4P8T6X9: 沒列錯，用夾的看看？上限是 T(n)=2T(n-1)+3
→ A4P8T6X9: 下限是T(n)=2T(n-2)+3,會在這兩個中間，這兩個都是2^n吧
推 yorunohoshi: http://i.imgur.com/fMan9Xf.jpg 用遞迴樹加猜測可
→ yorunohoshi: 以得出O(2^n) 但是用離散的做法應該才叫最tight的
→ yorunohoshi: http://i.imgur.com/6CWzL0l.jpg 離散算出來的bound
→ yorunohoshi: ed跟原本的費氏數列一樣就是黃金比例的n次方
推 yorunohoshi: 所以我覺得答案有瑕疵0.0
→ gary19941208: 謝謝樓上兩位！