开始效仿@cht大佬的标题格式了……
咳咳……
今天我们来讲解一下俗称搞死校园的
$$高斯消元$$
据说这玩意儿很高级,但是放在《算法竞赛进阶指南》里让人有一种恐惧感(因为它被放在数论里……)。。。。。。
这玩意儿我看了千次万次看不懂,但是后来豁然开朗!
任何算法都不难,不要觉得它很复杂,你自己推导一遍就懂了。 ——我的老师
高斯消元也一样,不要看着一大堆公式烦死,其实它也就四个步骤而已。
我们先来看一下高斯消元的过程:
图中那三个方框就是高斯消元中的“系数矩阵”,我们先看第三个方框。
可以看到第三个“对角矩阵”对角的这一条线,系数都是1。
所以等式的另一边就是方程的解。
可是如何将随机系数矩阵转化为上三角矩阵,又如何将上三角矩阵转化为对角矩阵呢?
了解了高斯消元的过程,我们就可以开始详细地说明具体过程了。
我们可以先从枚举列的角度考虑:
-
找主元
- 主元就是这一列里绝对值最大的一个。
- 注意一定是最大!
-
交换
- 将主元所在的一行交换到系数矩阵的最上方。
-
归一
- 把这一行的第一个数化为1。
- 但是如何操作呢?
- 也就是等式两边同时除以第一个系数。
-
消元
- 将后面所有行的这一列消成0。
注意!
因为高斯消元里面有除法,所以要用$double$存储!!!
时间复杂度$O(n^3)$
拿球形空间产生器这题为例吧!
实际上高斯消元其实并不难对吧hh
球形空间产生器
任何算法都不难,不要觉得它很复杂,你自己推导一遍就懂了。
这句话好经典呀
hhhh
确实并不难,我只搞了三个半小时就把它弄出来了……
我搞了四小时呀!!!
应该是三个半月打错了