作者shinle14 ()
看板Grad-ProbAsk
標題[理工] 中央108
時間Sun Jan 26 21:29:23 2020
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1580045365.A.FEF.html
1F：推 Aa841018: can find代表存在，也就是，如果不用DP可以成立的話， 01/26 22:21
2F：→ Aa841018: 那就是true 01/26 22:21
3F：推 ok8752665: 這題應該是討論漸進線 01/26 22:49
那這樣的話b為什麼對 如果都是指數
5F：推 mistel: 我以為這題是在說Fibonacci數字本身 01/26 22:56
※ 編輯: shinle14 (111.82.50.78 臺灣), 01/26/2020 22:58:08
6F：→ DLHZ: 不算漸近線 你只要符合他說的就好 01/26 23:03
7F：→ ok8752665: 我記得林瑋是說漸進線 有錯找他 lower bound本來就可 01/26 23:04
8F：→ ok8752665: 往下巴 01/26 23:04
9F：→ DLHZ: 對所有fib 可以有個指數函數為上界(ex: 100^n) 也可以為下界 01/26 23:05
10F：→ DLHZ: (ex: 0.01^n) 或有線性函數為下界 01/26 23:05
11F：→ DLHZ: 可由他的close form推得 01/26 23:06
12F：→ DLHZ: Fn=Ω(((1+√5)/2)^(n-2)) 裡面那串顯然遠大於任一線性函數 01/26 23:11
13F：→ DLHZ: 你可能誤會漸近線的意思了 01/26 23:13
14F：推 ok8752665: 不過 看起來確實滿像漸進線的 不然這個數列有漸進線嗎 01/26 23:21
15F：→ mathtsai: 題目問數字本身 01/26 23:28
16F：→ DLHZ: 這個...我也不知道這種的怎麼算XD 01/27 01:55