高斯消元变换和征服算法的替代方法

Question

变换和征服中的高斯消元算法具有O（n ）复杂度。是否有任何技术可以提供更高效的算法复杂度？

Answer 1

有更好的渐近的复杂性，例如，Strassen的算法的复杂性为O（n ^2.807）和Coppersmith–Winograd algorithm与复杂性为O（n ^2.376）算法的矩阵求逆。

（需要注意的是矩阵乘法和矩阵求逆的复杂性the same）

Answer 2

这取决于你衡量其复杂性：

乘法数：没有，通过改变技术，你只能恶化的复杂性高斯消元法。

时间步数：是的，并行实现行操作将时间复杂度降低到O（n）。