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

[juan19283746 (小阮)]

98 NCTU CSIE


(c) O(nlogn) + Θ(nlogn) = O(nlogn)


想請問在"各校攻略秘笈"裡會說他是錯的


想聽聽各位的看法


謝謝

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.40.93.59
推 mqazz1:不知能不能這樣想
→ mqazz1:upper bound + tight bound 應該選tight bound ?
推 christianSK:我覺得是兩個函數相加 bound未必是由比較大的決定
→ christianSK:不過我沒有想到例子@@
推 volleyer:感覺上是  兩個相加要取較大的那個
→ volleyer:O(nlogn)是收集複雜度≦nlogn的 (有可能n、logn、...etc)
推 volleyer:不過...Θ(nlogn)成立代表O(nlogn)也成立  所以感覺也不
→ volleyer:不能說他錯...(可能是要盡量嚴謹吧)
推 christianSK:V大說的很有道理!!
→ juan19283746:終於找到有人跟我一樣的想法了 謝啦
推 satics:假設前面的O(nlogn)的部分取n,Θ(nlogn)的部分取nlogn
→ satics:相加後big-O是Θ(nlogn)
推 torf:upper bound包含tight bound但"不等於"tight bound
→ sneak: upper bound https://muxiv.com
→ sneak: upper bound https://daxiv.com
→ sneak: O(nlogn)是收集 https://noxiv.com