→ MASAGA: 因為是bounded 所以不能取上界吧 01/05 20:00
→ MASAGA: 就像n=O(2^n) 但n還是polynomial 01/05 20:01
您好，我想問的問題如下:
已知lg(n!) = Θ(n*lg n)
1. (lg n)! is not Polynomailly Bounded
lg(lg n)! = Θ(lg n * lg (lg n))
= Θ(lg n * lglg n)
= ω(lg n)
因為lg(lg n)! != O(lg n)，所以(lg n)! 不是 Polynomail-Bounded
2. (lglg n)! is Polynomailly Bounded
lg(lglg n)! = Θ(lglg n * lg (lglg n))
= O((lglg n)^2)
= O(lg^2(lg n))
= O(lg n)
因為lg(lglg n)! = o(lg n)，所以(lglg n)!是Polynomail-Bounded
Q: 關於1.中的敘述，lg(lg n)!是否可以取
log(log n)! = Θ(lg n * lglg n)
= O((lg n)^2) = O(lg^2 n)
然後就說明因為lg(f(n)) != O(lg n)，所以f(n)不是Polynomail-Bounded?
還是說得要取little-omega，找到lg(f(n)) > ω(lgn)，
才可以說明不是Polynomail-Bounded?
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 120.126.33.178 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1578212655.A.6A1.html
※ 編輯: x411066 (120.126.33.178 臺灣), 01/05/2020 16:38:31