Re: [問題] 時間複雜度比較
※ 引述《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
→
12/31 17:02, , 1F
12/31 17:02, 1F
→
12/31 17:02, , 2F
12/31 17:02, 2F
討論串 (同標題文章)