作者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/cn.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