[理工] 线代子嘉1-108第99(c) EXPCDR PTT批踢踢实业坊

楼主: EXPCDR (EXPCDR) 2018-04-21 16:19:16

想请问为什么第99题的c答案是True
他指的意思是我图二写的那样吗？
大家是怎么想这题的复杂度是m^3的呢？
图一
https://i.imgur.com/6So3Yqp.jpg
图二
https://i.imgur.com/kxAFXwZ.jpg

作者: plsmaop (plsmaop) 2018-04-21 16:45:00

m^2 = O(m^3)?

作者: wilson50101 (我觉得我还不错啊) 2018-04-21 16:53:00

我的理解是A有m*m项高斯消去法一次至少可以消一项所以要消m^2次那m^2 =O(n)^2=O(n^3)好奇的是所以如果写O(n^2)也要对？

楼主: EXPCDR (EXPCDR) 2018-04-21 18:23:00

会不会是每消一项需要n次时间，有n^2项要消所以需要n^3 ?

作者: wilson50101 (我觉得我还不错啊) 2018-04-21 18:40:00

消一项只需要O(1)把

楼主: EXPCDR (EXPCDR) 2018-04-21 18:45:00

消一项就需要消掉一列，这样是n吧？

作者: wilson50101 (我觉得我还不错啊) 2018-04-21 18:54:00

喔对我想错了的确要花O(n)所以就刚好是o(n^3没错)

继续阅读