[理工] 線代子嘉1-108第99(c)

看板Grad-ProbAsk作者 (EXPCDR)時間6年前 (2018/04/21 16:19), 編輯推噓4(4推 0噓 9→)
留言13則, 3人參與, 6年前最新討論串1/1
想請問為什麼第99題的c答案是True 他指的意思是我圖二寫的那樣嗎？ 大家是怎麼想這題的複雜度是m^3的呢？ 圖一 https://i.imgur.com/6So3Yqp.jpg
圖二 https://i.imgur.com/kxAFXwZ.jpg
-- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 140.120.242.2 ※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1524298758.A.0B8.html
推
04/21 16:45, 6年前 , 1F
m^2 = O(m^3)?
04/21 16:45, 1F
推
04/21 16:53, 6年前 , 2F
我的理解是
04/21 16:53, 2F
→
04/21 16:53, 6年前 , 3F
A有m*m項
04/21 16:53, 3F
→
04/21 16:53, 6年前 , 4F
高斯消去法一次至少可以消一項所以要消m^2次
04/21 16:53, 4F
→
04/21 16:53, 6年前 , 5F
那m^2 =O(n)^2=O(n^3)
04/21 16:53, 5F
→
04/21 16:53, 6年前 , 6F
好奇的是
04/21 16:53, 6F
→
04/21 16:53, 6年前 , 7F
所以如果寫O(n^2)也要對？
04/21 16:53, 7F
→
04/21 18:23, 6年前 , 8F
會不會是每消一項需要n次時間，有n^2項要消所以需要n^3 ?
04/21 18:23, 8F
推
04/21 18:40, 6年前 , 9F
消一項只需要O(1)把
04/21 18:40, 9F
→
04/21 18:45, 6年前 , 10F
消一項就需要消掉一列，這樣是n吧？
04/21 18:45, 10F
推
04/21 18:54, 6年前 , 11F
喔對 我想錯了
04/21 18:54, 11F
→
04/21 18:54, 6年前 , 12F
的確要花O(n)
04/21 18:54, 12F
→
04/21 18:55, 6年前 , 13F
所以就剛好是o(n^3沒錯)
04/21 18:55, 13F
‣ 更多 EXPCDR 的文章
文章代碼(AID): #1QslG62u (Grad-ProbAsk)