看板 [ Prob_Solve ]
討論串[問題] 時間複雜度比較
共 2 篇文章
內容預覽： 開啟 | 關閉 | 只限未讀
首頁
上一頁
1
下一頁
尾頁
#1
[問題] 時間複雜度比較
推噓1(1推 0噓 3→)留言4則，0人參與, 最新作者s97610017 (粥有兪)時間12年前 (2011/12/31 16:15), 編輯資訊
1
0
0
內容預覽:
想請問. 1.. (lg n)! 和 n^3. 這兩個怎麼比大小?. 我看演算法的書(補習班的). 上面是(lg n)! > n^3. 但是我不知道怎麼比較出來的. 然後書上有個定理我也不太懂. 對所有k,a,b屬於R+. 以a為底的(㏒n)^b = o(n^k). 拜託大大們幫我了感謝~. --.
#2
Re: [問題] 時間複雜度比較
推噓0(0推 0噓 2→)留言2則，0人參與, 最新作者LPH66 (-858993460)時間12年前 (2011/12/31 16:55), 編輯資訊
0
0
0
內容預覽:
這樣做: 令 k = lg n 則 n = 2^k. 則 (lg n)! = k!, n^3 = 2^3k. 然後再取 lg. 由於 lg (k!) = Θ(k lg k) ←這個式子對排序演算法的下界證明很重要，值得一記. lg (2^3k) = 3k = Θ(k). 因此前者大於後者. 你要先懂
(還有452個字)
首頁
上一頁
1
下一頁
尾頁