[理工] 線代子嘉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沒錯)

繼續閱讀