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