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