[理工] 中央108

看板Grad-ProbAsk作者時間5年前 (2020/01/26 21:29), 5年前編輯推噓4(4推 0噓 12→)
留言16則, 5人參與, 5年前最新討論串1/1
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
推
01/26 22:21, 5年前 , 1F
can find代表存在，也就是，如果不用DP可以成立的話，
01/26 22:21, 1F
→
01/26 22:21, 5年前 , 2F
那就是true
01/26 22:21, 2F
推
01/26 22:49, 5年前 , 3F
這題應該是討論漸進線
01/26 22:49, 3F
那這樣的話b為什麼對 如果都是指數
→
01/26 22:50, 5年前 , 4F
https://tinyurl.com/t6t5r68 所以都是指數
01/26 22:50, 4F
推
01/26 22:56, 5年前 , 5F
我以為這題是在說Fibonacci數字本身
01/26 22:56, 5F
※ 編輯: shinle14 (111.82.50.78 臺灣), 01/26/2020 22:58:08
→
01/26 23:03, 5年前 , 6F
不算漸近線 你只要符合他說的就好
01/26 23:03, 6F
→
01/26 23:04, 5年前 , 7F
我記得林瑋是說漸進線 有錯找他 lower bound本來就可
01/26 23:04, 7F
→
01/26 23:04, 5年前 , 8F
往下巴
01/26 23:04, 8F
→
01/26 23:05, 5年前 , 9F
對所有fib 可以有個指數函數為上界(ex: 100^n) 也可以為下界
01/26 23:05, 9F
→
01/26 23:05, 5年前 , 10F
(ex: 0.01^n) 或有線性函數為下界
01/26 23:05, 10F
→
01/26 23:06, 5年前 , 11F
可由他的close form推得
01/26 23:06, 11F
→
01/26 23:11, 5年前 , 12F
Fn=Ω(((1+√5)/2)^(n-2)) 裡面那串顯然遠大於任一線性函數
01/26 23:11, 12F
→
01/26 23:13, 5年前 , 13F
你可能誤會漸近線的意思了
01/26 23:13, 13F
推
01/26 23:21, 5年前 , 14F
不過 看起來確實滿像漸進線的 不然這個數列有漸進線嗎
01/26 23:21, 14F
→
01/26 23:28, 5年前 , 15F
題目問數字本身
01/26 23:28, 15F
→
01/27 01:55, 5年前 , 16F
這個...我也不知道這種的怎麼算XD
01/27 01:55, 16F
‣ 更多 shinle14 的文章
文章代碼(AID): #1UBPGr_l (Grad-ProbAsk)