[理工] [ALGO] 比較複雜度

看板Grad-ProbAsk作者 (GO)時間15年前 (2011/02/19 22:43), 編輯推噓5(5推 0噓 8→)
留言13則, 7人參與, 最新討論串1/1
請問n/logn 跟 n^1/2 哪個比較大呢?? 取log完是logn-loglogn vs. 1/2logn 所以我是選一樣大啦 正確答案是? -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.230.70
→
02/19 22:45, , 1F
logn 比 n^0.00000000000000001 都小
02/19 22:45, 1F
→
02/19 22:49, , 2F
所以答案是?? 小弟比較笨 不好意思= =
02/19 22:49, 2F
→
02/19 22:50, , 3F
n/logn
02/19 22:50, 3F
→
02/19 22:52, , 4F
分母的logn無視的意思嗎
02/19 22:52, 4F
推
02/19 22:55, , 5F
可以用limit+羅畢達推出來,但較麻煩
02/19 22:55, 5F
推
02/19 22:59, , 6F
應該是n/logn大
02/19 22:59, 6F
→
02/19 22:59, , 7F
但我想問 為什麼直接取log兩邊會在同一bound
02/19 22:59, 7F
推
02/19 23:02, , 8F
應該是取完一樣不一定原來一樣
02/19 23:02, 8F
→
02/19 23:03, , 9F
取完不一樣原來就不一樣,不太確定@@ 高手請指正~
02/19 23:03, 9F
推
02/19 23:13, , 10F
恩..查一下筆記 沒錯 那只是必要條件~
02/19 23:13, 10F
推
02/19 23:13, , 11F
1/2*logn vs logn-loglogn 這邊常數不能忽略像
02/19 23:13, 11F
→
02/19 23:14, , 12F
n^2 與 n^3會變成 2logn 3logn 常數不能忽略..
02/19 23:14, 12F
→
09/11 14:17, , 13F
恩..查一下筆記 沒 https://daxiv.com
09/11 14:17, 13F
‣ 更多 QoiiwWe 的文章
文章代碼(AID): #1DNzSCe7 (Grad-ProbAsk)