PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 時間複雜度比較

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (-858993460)時間13年前 (2011/12/31 16:55)推噓0(0推 0噓 2→)

留言2則, 1人參與討論串2/2 (看更多)

※ 引述《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