作者fmtshk (fmtshk)
看板Grad-ProbAsk
标题[理工] 资结_一题复杂度求解答
时间Wed Jan 8 21:07:15 2020
https://i.imgur.com/7ZhKa9H.jpg
这题^_^
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.12.106.28 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1578488837.A.630.html
1F：→ DLHZ: 你不是写在上面了吗 01/08 22:03
2F：→ fmtshk: 对自己答案没信心 01/08 22:41
3F：推 Aa841018: 我觉得如果8xlog(y^4)/8的x大到和2^2y相等或更大，那复 01/08 22:58
4F：→ Aa841018: 杂度有可能超过2^2y 01/08 22:58
5F：→ DLHZ: 对欸 那应该是O(8xlog...+2^2y) 01/08 23:06
6F：推 bochengchen: 照Ａ大的想法的话！最後的10xcosx也要算进去吧！ 01/08 23:18
7F：→ DLHZ: 我决定答案是O(2^2y+10xcosx) 01/08 23:21
8F：推 Aa841018: 10xcosx会被8xlog(y^4)/8包进去吧？cosx基本上就是常数 01/08 23:46
9F：→ Aa841018: 而已，我觉得答案是O(max(2^2y,xlogy)) 01/08 23:46
10F：→ realmanKG: 把x, y视为同地位的变数，我会选2^2y，上面讲的x大到 01/09 10:22
11F：→ realmanKG: 跟2^2y的差不多的情况会有点怪，终究一个是polynomial 01/09 10:22
12F：→ realmanKG: 一个是exponential 01/09 10:22
13F：推 ok8752665: 我也觉得是2^2y 看起来x,y都是变数 那都趋近於无穷大的 01/09 10:45
14F：→ ok8752665: 情况下 应该是2^2y影响最大 01/09 10:45
15F：推 mi981027: 双变数函数的asymptotic是存在c, x0, y0 > 0 01/09 11:15
16F：→ mi981027: 使得对於所有x > x0, y > y0 f(x,y) <= c*g(x,y) 01/09 11:15
17F：→ mi981027: 如果答案是2^2y的话 表示 存在c,x0, y0 使得对於 01/09 11:15
18F：→ mi981027: 所有x>x0, y> y0, xlogy + 2^2y <= c*2^2y这个不合理 01/09 11:15
19F：→ mi981027: 所以我觉得A大那个答案才对 但我会写O(xlogy+4^y) 01/09 11:15
20F：→ DLHZ: 我想法是y大的话有y^2y来包含 x大的话有10x来包含(或xlogy) 01/09 12:32
21F：→ DLHZ: 那这样是不是两个都行？ 01/09 12:32
22F：推 zuchang: x大的话 x Logy 应该还是比10x 大 以成长性看的话 01/09 12:56
23F：→ DLHZ: 可是如果单看x 对x偏微两个斜率不都在常数倍内吗 01/09 13:15
24F：→ realmanKG: 谢mi大释疑，我支持O(xlogy+4^y)这个答案 01/09 21:30