[理工] 資結_一題複雜度求解答

看板Grad-ProbAsk作者 (fmtshk)時間6年前 (2020/01/08 21:07), 編輯推噓6(6推 0噓 18→)
留言24則, 8人參與, 6年前最新討論串1/1
https://i.imgur.com/7ZhKa9H.jpg
這題^_^ -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 39.12.106.28 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578488837.A.630.html
→
01/08 22:03, 6年前 , 1F
你不是寫在上面了嗎
01/08 22:03, 1F
→
01/08 22:41, 6年前 , 2F
對自己答案沒信心
01/08 22:41, 2F
推
01/08 22:58, 6年前 , 3F
我覺得如果8xlog(y^4)/8的x大到和2^2y相等或更大，那複
01/08 22:58, 3F
→
01/08 22:58, 6年前 , 4F
雜度有可能超過2^2y
01/08 22:58, 4F
→
01/08 23:06, 6年前 , 5F
對欸 那應該是O(8xlog...+2^2y)
01/08 23:06, 5F
推
01/08 23:18, 6年前 , 6F
照Ａ大的想法的話！最後的10xcosx也要算進去吧！
01/08 23:18, 6F
→
01/08 23:21, 6年前 , 7F
我決定答案是O(2^2y+10xcosx)
01/08 23:21, 7F
推
01/08 23:46, 6年前 , 8F
10xcosx會被8xlog(y^4)/8包進去吧？cosx基本上就是常數
01/08 23:46, 8F
→
01/08 23:46, 6年前 , 9F
而已，我覺得答案是O(max(2^2y,xlogy))
01/08 23:46, 9F
→
01/09 10:22, 6年前 , 10F
把x, y視為同地位的變數，我會選2^2y，上面講的x大到
01/09 10:22, 10F
→
01/09 10:22, 6年前 , 11F
跟2^2y的差不多的情況會有點怪，終究一個是polynomial
01/09 10:22, 11F
→
01/09 10:22, 6年前 , 12F
一個是exponential
01/09 10:22, 12F
推
01/09 10:45, 6年前 , 13F
我也覺得是2^2y 看起來x,y都是變數 那都趨近於無窮大的
01/09 10:45, 13F
→
01/09 10:45, 6年前 , 14F
情況下 應該是2^2y影響最大
01/09 10:45, 14F
推
01/09 11:15, 6年前 , 15F
雙變數函數的asymptotic是存在c, x0, y0 > 0
01/09 11:15, 15F
→
01/09 11:15, 6年前 , 16F
使得對於所有x > x0, y > y0 f(x,y) <= c*g(x,y)
01/09 11:15, 16F
→
01/09 11:15, 6年前 , 17F
如果答案是2^2y的話 表示 存在c,x0, y0 使得對於
01/09 11:15, 17F
→
01/09 11:15, 6年前 , 18F
所有x>x0, y> y0, xlogy + 2^2y <= c*2^2y這個不合理
01/09 11:15, 18F
→
01/09 11:15, 6年前 , 19F
所以我覺得A大那個答案才對 但我會寫O(xlogy+4^y)
01/09 11:15, 19F
→
01/09 12:32, 6年前 , 20F
我想法是y大的話有y^2y來包含 x大的話有10x來包含(或xlogy)
01/09 12:32, 20F
→
01/09 12:32, 6年前 , 21F
那這樣是不是兩個都行？
01/09 12:32, 21F
推
01/09 12:56, 6年前 , 22F
x大的話 x Logy 應該還是比10x 大 以成長性看的話
01/09 12:56, 22F
→
01/09 13:15, 6年前 , 23F
可是如果單看x 對x偏微兩個斜率不都在常數倍內嗎
01/09 13:15, 23F
→
01/09 21:30, 6年前 , 24F
謝mi大釋疑，我支持O(xlogy+4^y)這個答案
01/09 21:30, 24F
‣ 更多 fmtshk 的文章
文章代碼(AID): #1U5TG5Om (Grad-ProbAsk)