作者wang19980531 (柯黑戰神 第一英粉)
看板Grad-ProbAsk
標題[理工] 資結 時間複雜度 2題
時間Sat Jul 27 22:46:30 2019
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://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1564238792.A.D2C.html
1F：推 james80351: 第一題就取log 最後要推到O(log n)呀 07/28 00:10
3F：→ JKLee: =是指集合的belong還是equual 07/28 00:12
4F：→ JKLee: ? 07/28 00:12
5F：→ mistel: 第二題我不知道 因為這是定理，但我覺得也成立就是了... 07/28 00:13
6F：推 mistel: 樓上，是集合的belong 07/28 00:16
7F：→ JKLee: 若是equal,則c錯 07/28 00:16
8F：→ JKLee: 若是belong,則c對 07/28 00:17
9F：→ wang19980531: 謝謝大家 07/28 14:13
10F：推 ekids1234: 為何 equal 錯呀 07/28 17:44
11F：→ wang19980531: 對耶 剛看了一下 theta(nlogn)不就表示平均是nlogn 07/28 20:48
12F：→ wang19980531: 那麼說複雜度最少就是O(nlogn)吧？ 07/28 20:48
14F：→ jls16457: 順帶一提，theta跟跟平均應該是不一樣的哦 07/28 22:00
15F：→ wang19980531: 意思是 theta(n) <=> O(n)and omega (n) 07/29 10:41
16F：→ wang19980531: 所以C已經確認範圍是夾集 應該要寫theta(nlogn) ? 07/29 10:41