作者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/cn.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