為什麼這篇餘因子矩陣計算機鄉民發文收入到精華區：因為在餘因子矩陣計算機這個討論話題中，有許多相關的文章在討論，這篇最有參考價值！作者skyHuan (Huan)看板Grad-ProbAsk標題[理工] 線代 行列式計算的複雜度時...
計算行列式值
用降階遞迴的方法複雜度是O(n!)
因為矩陣做列運算行列式值只會改變倍數
所以可以列運算到上三角矩陣計算行列式值
這時候複雜度就跟高斯消去法一樣是O(n^3)
https://imgur.com/4NF1Gg9.jpg
可以跟矩陣的乘法達到相同的複雜度
Strassen's algo: O(n^2.376)
我的問題是
1. 為什麼高斯消去法的複雜度是O(n^3)
2. 為什麼行列式的計算可以跟矩陣乘法達到相同複雜度，這是代表兩者等價的意思嗎
感謝解答
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.140.59.53
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1537422022.A.A52.html
推 y2j60537: 第一題我的理解是這樣09/20 16:40
→ y2j60537: 第二題等高手解答09/20 16:40
1.原來是做一次列運算複雜度O(n)！2.的部分我想到跟乘法直接有關的
(1) A‧adj(A)=det(A)‧I
所以是求A‧adj(A)第(i,i)項
但求餘因子也要算行列式
(2) A列運算到U，存在P使得PA=U
算U的行列式值等於PA的複雜度
但要得到P要做高斯消去法
複雜度好像還是不可能低於O(n^3)
※ 編輯: skyHuan (223.140.59.53), 09/20/2018 21:12:52