[理工] 線代 行列式計算的複雜度
計算行列式值
用降階遞迴的方法複雜度是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
推
09/20 16:40,
5年前
, 1F
09/20 16:40, 1F
→
09/20 16:40,
5年前
, 2F
09/20 16:40, 2F
→
09/20 16:40,
5年前
, 3F
09/20 16:40, 3F
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