刚才想着把算法复杂度降为O(n^2)，但其实对于第i+1行~第n行加上第k行*一个系数，第k行的各个数的值不是相等的，是我想多了……………………

 

程序：

AX=B，已知A,B，求X

A(i,j) i>=j 都不用处理

 

1.化为上三角矩阵 (实际上是A(i,j) [i>=j] 被忽略)

2.根据上三角矩阵求出结果X1~Xn

 

时间复杂度：

对于“ a[j][k]+=value*a[i][k]; ”

(n-1)*n + (n-2)*(n-1) + … +  1*2 = (n-1)*n*(n+1)/3

 

对于“ a[j][n+1]-=x[i]*a[j][i]; ”

(n-1) + (n-2) + … + 1 = (n-1)*n/2

 

！！！有时更快的方法：

CA=A' (其中A’为上文所说的上三角矩阵)

其中C(j,i)=-A(j,i)/A(i,i)    [j>i]　　即把第i行的部分数加入第i+1行~第n行，

然后其它的值为0，因为无意义。

矩阵乘法的时间复杂度为O(n^r) r=2.376 etc.

 

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #define cha 1e-10 5  6 double a[1000][1000],x[1000]; 7 int main() 8 { 9     long n,i,j,k;10     double temp,value;11     scanf("%ld",&n);12     for (i=1;i<=n;i++)13         for (j=1;j<=n;j++)14             scanf("%lf",&a[i][j]);15     for (i=1;i<=n;i++)16         scanf("%lf",&a[i][n+1]);17 18     for (i=1;i<=n;i++)19     {20         //找到第i列从第i行开始第一个值不为0的数21         if (fabs(a[i][i])
        
         cha)25                     break;26             //交换第i行和第j行27             for (k=1;k<=n;k++)28             {29                 temp=a[i][k];30                 a[i][k]=a[j][k];31                 a[j][k]=temp;32             }33         }34         for (j=i+1;j<=n;j++)35         {36             value=-a[j][i]/a[i][i]; //避免后面“a[j][k]-=value*a[i][k];”求多次补码37             for (k=i+1;k<=n+1;k++)  //n+1:结果也要进行处理38                 a[j][k]+=value*a[i][k];39         }40     }41     for (i=n;i>=1;i--)42     {43         x[i]=a[i][n+1]/a[i][i];44         for (j=i-1;j>=1;j--)45             a[j][n+1]-=x[i]*a[j][i];46     }47     for (i=1;i<=n;i++)48         printf("%.2lf ",x[i]);49     return 0;50 }51 /*52 353 2 1 154 6 2 155 -2 2 156 1 -1 757 58 -1.00 2.00 1.0059 */