作者skyHuan (Huan)
看板Grad-ProbAsk
标题[理工] 线代 行列式计算的复杂度
时间Thu Sep 20 13:40:20 2018
计算行列式值
用降阶递回的方法复杂度是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://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1537422022.A.A52.html
1F：推 y2j60537: 第一题我的理解是这样09/20 16:40
3F：→ 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