作者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://www.ptt.cc/bbs/Grad-ProbAsk/M.1560688416.A.C37.html
推 kyuudonut: Big-O 只是拿來評估演算法的複雜度,但當複雜度的處於 06/28 14:42
→ kyuudonut: 同一個數量級時 (如此例 O(n^2)),最好還是去估算實際 06/28 14:42
→ kyuudonut: 執行的 operation 個數才合理。就像你現在查覺到的問題 06/28 14:43
→ kyuudonut: 一樣。透過 Big-O 我們無法去了解係數這個 factor 影響 06/28 14:43
→ kyuudonut: 多少 06/28 14:43
推 kyuudonut: 這張表格的註解 ...... 參考就好 06/28 14:47
→ ok8752665: 豪 謝謝你 06/28 17:03