作者s97610017 (粥有兪)
看板Prob_Solve
标题[问题] 时间复杂度比较
时间Sat Dec 31 16:15:50 2011
想请问
1.
(lg n)! 和 n^3
这两个怎麽比大小?
我看演算法的书(补习班的)
上面是(lg n)! > n^3
但是我不知道怎麽比较出来的
然後书上有个定理我也不太懂
对所有k,a,b属於R+
以a为底的(㏒n)^b = o(n^k)
拜托大大们帮我了感谢~
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 175.181.119.47
1F：推 springman:假设 n = 2^k，则 (lg n)! = k!，而 n^3 = 2^{3k} 12/31 16:46
2F：→ springman:k! 当然比 2^{3k} 大，都取 lg 的话 12/31 16:46
3F：→ springman:lg k! = k lg k，而 lg(2^{3k}) = 3k 12/31 16:47
4F：→ s97610017:了解了~十分感谢春天大大~^^ 12/31 17:00