问Gram-Schmidt正交化算法的计算复杂度

EN

点积采用m-1加法和m乘.

向量归一化采用1个向量平方(点积)，1个平方根和m个除法。

m-1 +, m *, m /, 1 √

向量投影的减法采用1点乘积，m乘和m加法，即

2m-1 +, 2m *

计算j-向量需要(j-1)减去投影，然后进行归一化，即

(2m-1)(j-1)+m-1 +, 2m(j-1)+m *, m /, 1 √

计算从j=1到k的向量，因此因子(j-1)变成三角形数(k-1)k/2，与j无关的项乘以k：

(2m-1)(k-1)k/2+(m-1)k +, 2m(k-1)k/2+mk *, mk /, k √

在点乘积中，m除法可以用逆乘积来交换m乘积，从而获得收益。

(2m-1)(k-1)k/2+(m-1)k +, 2m(k-1)k/2+2mk *, k /, k √

所以基本上是2mk的运算。

Gram算法的总体复杂性是O(m.k^2)：

这个过程必须应用k次，并且每一次正交化都需要O(m.k)运算(乘法和加法)，因此它使O(m.k^2)变得复杂起来。