[理工] 中央108 shinle14 PTT批踢踢實業坊

作者: shinle14 2020-01-26 21:29:23

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

作者: Aa841018 (andrew) 2020-01-26 22:21:00

can find代表存在，也就是，如果不用DP可以成立的話，那就是true

作者: ok8752665 (dd8752665) 2020-01-26 22:49:00

這題應該是討論漸進線https://tinyurl.com/t6t5r68 所以都是指數

作者: mistel (Mistel) 2020-01-26 22:56:00

我以為這題是在說Fibonacci數字本身

作者: DLHZ ( ) 2020-01-26 23:03:00

不算漸近線你只要符合他說的就好

作者: ok8752665 (dd8752665) 2020-01-26 23:04:00

我記得林瑋是說漸進線有錯找他 lower bound本來就可往下巴

作者: DLHZ ( ) 2020-01-26 23:05:00

對所有fib 可以有個指數函數為上界(ex: 100^n) 也可以為下界(ex: 0.01^n) 或有線性函數為下界可由他的close form推得Fn=Ω(((1+√5)/2)^(n-2)) 裡面那串顯然遠大於任一線性函數你可能誤會漸近線的意思了

作者: ok8752665 (dd8752665) 2020-01-26 23:21:00

不過看起來確實滿像漸進線的不然這個數列有漸進線嗎

作者: mathtsai (mathtsai) 2020-01-26 23:28:00

題目問數字本身

作者: DLHZ ( ) 2020-01-27 01:55:00

這個...我也不知道這種的怎麼算XD

繼續閱讀