[理工] 中央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

继续阅读