[問題] 時間複雜度比較

看板Prob_Solve作者 (粥有兪)時間12年前 (2011/12/31 16:15), 編輯推噓1(1推 0噓 3→)
留言4則, 2人參與, 最新討論串1/2 (看更多)
想請問 1. (lg n)! 和 n^3 這兩個怎麼比大小? 我看演算法的書(補習班的) 上面是(lg n)! > n^3 但是我不知道怎麼比較出來的 然後書上有個定理我也不太懂 對所有k,a,b屬於R+ 以a為底的(㏒n)^b = o(n^k) 拜託大大們幫我了感謝~ -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 175.181.119.47
推
12/31 16:46, , 1F
假設 n = 2^k，則 (lg n)! = k!，而 n^3 = 2^{3k}
12/31 16:46, 1F
→
12/31 16:46, , 2F
k! 當然比 2^{3k} 大，都取 lg 的話
12/31 16:46, 2F
→
12/31 16:47, , 3F
lg k! = k lg k，而 lg(2^{3k}) = 3k
12/31 16:47, 3F
→
12/31 17:00, , 4F
瞭解了~十分感謝春天大大~^^
12/31 17:00, 4F
‣ 更多 s97610017 的文章
文章代碼(AID): #1E_iIxED (Prob_Solve)
‣ 更多 s97610017 的文章
文章代碼(AID): #1E_iIxED (Prob_Solve)