计算n×n矩阵行列式是否真需n!次运算？100×100矩阵运算量疑问

我太懂你这种一开始的想法了！刚接触行列式计算复杂度的时候，我也踩过一模一样的坑：

• 最开始琢磨100×100矩阵的行列式，直觉告诉我得要100!次运算——毕竟按最直接的递归展开逻辑：算100阶行列式，得先计算100个99阶矩阵的行列式，每个99阶又要计算99个98阶的，这么一层层递推下去，可不就是100!次运算吗？
• 当时我搜索的时候，看到不少计算机科学领域的人也这么说，那时候我更笃定这个结论是完全正确的。

但后来仔细琢磨才发现，这其实是陷入了最朴素的递归展开思路的误区，实际运算量能大幅降低，关键在于换个反向的思路——利用行列式的数学性质，用高斯消元法来计算！

具体来说，我们可以通过初等行变换把原矩阵转换成上三角矩阵，根据行列式的性质，这个过程只会改变行列式的符号（行交换时）或者保持值不变，而最终上三角矩阵的行列式就是对角线上所有元素的乘积。而高斯消元完成这个转换的时间复杂度是O(n³)，对于100×100的矩阵来说，就是100³=1,000,000次运算，和100!那个天文数字比起来，简直是天差地别。

之所以一开始会得出100!的结论，是因为我们默认使用了完全不利用数学性质的暴力递归展开法，而消元法正是抓住了行列式的核心性质，把原本指数级的复杂度直接降到了多项式级。

内容的提问来源于stack exchange，提问作者bilanush