[理工] 中央108

[shinle14 ()]

https://i.imgur.com/SvtmhNQ.jpg
請問第2題 答案給D可是我不知道為什麼是錯的 如果是用DP來做不是O(n)嗎？那為什麼會錯 反而是C選項 lower bound 最快如果是O(n)為啥可以說lowerbound是指數
-----
Sent from JPTT on my iPhone

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.50.78 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1580045365.A.FEF.html
推 Aa841018: can find代表存在，也就是，如果不用DP可以成立的話，
→ Aa841018: 那就是true
推 ok8752665: 這題應該是討論漸進線
那這樣的話b為什麼對 如果都是指數
→ ok8752665: https://tinyurl.com/t6t5r68 所以都是指數
推 mistel: 我以為這題是在說Fibonacci數字本身
※ 編輯: shinle14 (111.82.50.78 臺灣), 01/26/2020 22:58:08
→ DLHZ: 不算漸近線 你只要符合他說的就好
→ ok8752665: 我記得林瑋是說漸進線 有錯找他 lower bound本來就可
→ ok8752665: 往下巴
→ DLHZ: 對所有fib 可以有個指數函數為上界(ex: 100^n) 也可以為下界
→ DLHZ: (ex: 0.01^n) 或有線性函數為下界
→ DLHZ: 可由他的close form推得
→ DLHZ: Fn=Ω(((1+√5)/2)^(n-2)) 裡面那串顯然遠大於任一線性函數
→ DLHZ: 你可能誤會漸近線的意思了
推 ok8752665: 不過 看起來確實滿像漸進線的 不然這個數列有漸進線嗎
→ mathtsai: 題目問數字本身
→ DLHZ: 這個...我也不知道這種的怎麼算XD