[理工] [演算法] 時間複雜度 big-O

看板Grad-ProbAsk作者 (小阮)時間15年前 (2010/11/20 20:13), 編輯推噓7(7推 0噓 9→)
留言16則, 7人參與, 7年前最新討論串1/1
98 NCTU CSIE (c) O(nlogn) + Θ(nlogn) = O(nlogn) 想請問在"各校攻略秘笈"裡會說他是錯的 想聽聽各位的看法 謝謝 -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 114.40.93.59
推
11/20 20:52, , 1F
不知能不能這樣想
11/20 20:52, 1F
→
11/20 20:53, , 2F
upper bound + tight bound 應該選tight bound ?
11/20 20:53, 2F
推
11/20 20:54, , 3F
我覺得是兩個函數相加 bound未必是由比較大的決定
11/20 20:54, 3F
→
11/20 20:54, , 4F
不過我沒有想到例子@@
11/20 20:54, 4F
推
11/20 21:04, , 5F
感覺上是 兩個相加要取較大的那個
11/20 21:04, 5F
→
11/20 21:05, , 6F
O(nlogn)是收集複雜度≦nlogn的 (有可能n、logn、...etc)
11/20 21:05, 6F
推
11/20 21:10, , 7F
不過...Θ(nlogn)成立代表O(nlogn)也成立 所以感覺也不
11/20 21:10, 7F
→
11/20 21:11, , 8F
不能說他錯...(可能是要盡量嚴謹吧)
11/20 21:11, 8F
推
11/20 21:22, , 9F
V大說的很有道理!!
11/20 21:22, 9F
→
11/20 21:50, , 10F
終於找到有人跟我一樣的想法了 謝啦
11/20 21:50, 10F
推
11/24 00:42, , 11F
假設前面的O(nlogn)的部分取n,Θ(nlogn)的部分取nlogn
11/24 00:42, 11F
→
11/24 00:43, , 12F
相加後big-O是Θ(nlogn)
11/24 00:43, 12F
推
10/03 13:43, , 13F
upper bound包含tight bound但"不等於"tight bound
10/03 13:43, 13F
→
08/09 10:54, , 14F
upper bound https://muxiv.com
08/09 10:54, 14F
→
09/11 14:03, , 15F
upper bound https://daxiv.com
09/11 14:03, 15F
→
12/15 00:27, 7年前 , 16F
O(nlogn)是收集 https://noxiv.com
12/15 00:27, 16F
‣ 更多 juan19283746 的文章
文章代碼(AID): #1CvxjWMj (Grad-ProbAsk)