※ 引述《s97610017 (粥有兪)》之銘言： : 想請問 : 1. : (lg n)! 和 n^3 : 這兩個怎麼比大小? : 我看演算法的書(補習班的) : 上面是(lg n)! > n^3 : 但是我不知道怎麼比較出來的 這樣做: 令 k = lg n 則 n = 2^k 則 (lg n)! = k!, n^3 = 2^3k 然後再取 lg 由於 lg (k!) = Θ(k lg k) ←這個式子對排序演算法的下界證明很重要，值得一記 lg (2^3k) = 3k = Θ(k) 因此前者大於後者 : 然後書上有個定理我也不太懂 : 對所有k,a,b屬於R+ : 以a為底的(㏒n)^b = o(n^k) : 拜託大大們幫我了感謝~ 你要先懂小 o 的意義 f(n)=o(g(n)) 的定義是 ∀ε>0 ∃n0 ∀n>n0 |f(n)| < |g(n) * ε| 意思是 不管我把 g(n) 縮小多少倍 都會在某一點之後這縮小後的 g(n) 依然比 f(n) 大 也就是 f(n) 被 g(n) 給完全壓制 和大 O 的不同點在於大 O 只說在某一點之後 f(n) 被某個 g(n) 的倍數壓制而已 感覺上小 o 就是比我低幾級 不像大 O 可能是和我同級的 那這個定理的意思就是 不管 lgn 再怎麼取次方 終究都會被 n^k 給完全壓制 也就是「(lgn)^b 就是在 n^k 的下級」這種感覺 這代表就算是 (lgn)^1000 也是在 n^0.0001 的下級 -- 看你似乎是要準備考試的 那這篇就講到這裡就好 其他部份講下去大概會扯到不少有的沒的 那個我也沒把握能說得清楚就是... -- 有人喜歡邊玩遊戲邊上逼； 也有人喜歡邊聽歌邊打字。 但是，我有個請求， 選字的時候請專心好嗎？ -- 改編自「古 火田 任三郎」之開場白 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 140.112.30.83