[理工] 資結 時間複雜度 2題

[wang19980531 (柯黑戰神 第一英粉)]

1. 該如何說明
(loglogn)! 為一個polynomially bounded function?

2. 原題目如下，不曉得C為何錯誤
We abuse the “ + “ operator with asymptotic notations. For example , we may sa
y that the total time for an algorithm is O(n) + Θ(n). Which of the following s
tatement are true.
A. O(nlogn)+ Θ(n^2)= Θ(n^2)
B. O(n^2)+ Θ(n^2)= Θ(n^2)
C. O(nlogn)+ Θ(nlogn) = O(nlogn)
D. O(n^2)+O(nlogn)= Θ(n^2)

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.247.70.195 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1564238792.A.D2C.html
推 james80351: 第一題就取log 最後要推到O(log n)呀
推 mistel: https://i.imgur.com/XjSTD3O.jpg
→ JKLee: =是指集合的belong還是equual
→ JKLee: ?
→ mistel: 第二題我不知道 因為這是定理，但我覺得也成立就是了...
推 mistel: 樓上，是集合的belong
→ JKLee: 若是equal,則c錯
→ JKLee: 若是belong,則c對
→ wang19980531: 謝謝大家
推 ekids1234: 為何 equal 錯呀
→ wang19980531: 對耶 剛看了一下 theta(nlogn)不就表示平均是nlogn
→ wang19980531: 那麼說複雜度最少就是O(nlogn)吧？
→ jls16457: #1Nbmks0d
→ jls16457: 順帶一提，theta跟跟平均應該是不一樣的哦
→ wang19980531: 意思是 theta(n) <=> O(n)and omega (n)
→ wang19980531: 所以C已經確認範圍是夾集 應該要寫theta(nlogn) ?