作者x411066 (热开水)
看板Grad-ProbAsk
标题[理工] Aysmptotic Notations题目
时间Sun Jan 5 16:24:13 2020
您好，我想问的问题如下:
已知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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1578212655.A.6A1.html
※ 编辑: x411066 (120.126.33.178 台湾), 01/05/2020 16:38:31
1F：→ MASAGA: 因为是bounded 所以不能取上界吧 01/05 20:00
2F：→ MASAGA: 就像n=O(2^n) 但n还是polynomial 01/05 20:01