2012-08-21

線代1-108

請問一下第99題的C選項
為什麼是O(m^3)呢?
用高斯消去法應該分為2個階段(從上面往下面消跟返消回去)各為
(m-1)+(m-2)+...+2+1=O(m^2)
所以應該共是O(2*m^2)=O(m^2)
不知道我的想法錯在哪裡?謝謝
張貼者： 於

1 則留言:

月戀星辰 提到...

您好：
第一次消去時，複雜度是(m-1)(m-1)，第二次是(m-2)(m-1)、依此類推，因為每一個row都要(m-k)次加減法，k是第幾次消去，共有(m-1)列需要變動。
因為矩陣m*m，所以以上的消去共要做m次，故O(m^3)。

以上淺見..



2012年8月21日 晚上7:50

張貼留言

訂閱： 張貼留言 (Atom)