作者ok8752665 ()
看板Grad-ProbAsk
标题[理工] Big-O的问题
时间Sun Jun 16 20:33:34 2019
https://i.imgur.com/RY30gZA.png
像这张图 当e约为n(n-1)/2时 他把它当O(n^2)来看
所以O(n+e)=O(n+n^2)
因此会略比O(n^2)差
那这边我有个问题
他是因为把/2省略掉才看起来比较大
因为不删的话 n+n(n-1)/2 跟n^2比
当n越大 明显是左边比较小吧
所以实际上adj list都比较优吧
是嘛？
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 220.132.184.251 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1560688416.A.C37.html
1F：推 kyuudonut: Big-O 只是拿来评估演算法的复杂度，但当复杂度的处於 06/28 14:42
2F：→ kyuudonut: 同一个数量级时 (如此例 O(n^2))，最好还是去估算实际 06/28 14:42
3F：→ kyuudonut: 执行的 operation 个数才合理。就像你现在查觉到的问题 06/28 14:43
4F：→ kyuudonut: 一样。透过 Big-O 我们无法去了解系数这个 factor 影响 06/28 14:43
5F：→ kyuudonut: 多少 06/28 14:43
6F：推 kyuudonut: 这张表格的注解 ...... 参考就好 06/28 14:47
7F：→ ok8752665: 豪 谢谢你 06/28 17:03