[理工] 98交大polynomial bound問題

看板Grad-ProbAsk作者 (一塊錢)時間7年前 (2017/01/24 00:28), 編輯推噓0(009)
留言9則, 3人參與, 最新討論串1/1
請問98年交大第四題 補習班的書說nlogn是polynomial bound 但是log(n!)卻不是 是補習班寫錯了嗎? http://imgur.com/a/VMhuw 懇請各位指點 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 118.150.244.157 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1485188880.A.595.html

01/24 00:29, , 1F
他不是有寫?
01/24 00:29, 1F

01/24 00:29, , 2F
Log^2n後面那個就是呀
01/24 00:29, 2F

01/24 01:58, , 3F
不好意思 我眼殘
01/24 01:58, 3F

01/24 01:58, , 4F
不過nlogn 在取log為什麼是O(logn)
01/24 01:58, 4F

01/24 01:59, , 5F
按polynomial bound定義不是要取log等於O(logn)嗎
01/24 01:59, 5F

01/24 07:34, , 6F
想想看n^3和nlogn,兩邊同除n之後得到n^2和logn,顯然
01/24 07:34, 6F

01/24 07:35, , 7F
n^2比較大,所以nlogn是polynomialy bounded
01/24 07:35, 7F

01/24 07:35, , 8F
nlogn取log之後是log(nlogn)=logn+loglogn=O(logn)
01/24 07:35, 8F

01/24 09:30, , 9F
原來是這樣想的 解釋的很清楚 感謝
01/24 09:30, 9F
文章代碼(AID): #1OXYyGML (Grad-ProbAsk)