如何提高C中矩陣運算的效率？

Question

我有一個N*N上三角矩陣的屬性，它的所有對角元素是a1,a2,a3,...,aN。我想這a[i][j] (for all j>i) 應該

(a[i][j-1] + a[i+1][j])/2. 

我有很多的測試情況下，我必須每天來計算答案時應用此屬性。什麼是最佳的方式來做到這一點，所以對於所有的測試用例來說，整體運行時間會更少？測試用例：輸入是N and a1,a2,...,aN。

要算出答案，我需要做的：

a[0][0] + a[0][2] + ... + a[0][n-1] + a[2][n-1] + a[4][n-1] + ... + a[n-1][n-1]. 

我的解決方案（其中不斷得到超時）：

#include<stdio.h> 
double a[2000][2000]; 
int main(){ 
int test; 
scanf("%d",&test); 
//int arr[2000]; 
while(test--){ 
    int n,i,j; 
    //scanf("%d",&n); 
    scanf("%d",&n); 
    for(i=0;i<n;i++){ 
     int num; 
     scanf("%d",&num); 
     if(n!=1) 
      a[i][i] = num*0.5; 
     else 
      a[i][i] = num; 
    } 
    for(j=1;j<n;j++){ 
     int k=j; 
     for(i=0;i<n-j;i++,k++){ 
      if(i==0 && k==n-1) 
       a[i][k] = (a[i+1][k]+a[i][k-1]); 
      else 
       a[i][k] = (a[i+1][k]+a[i][k-1])*0.5; 
     } 
    } 
    float sum=0.0; 
    for(i=0;i<n;i+=2){ 
     if(i != n-1) 
     sum+=a[0][i]+a[n-1-i][n-1]; 
     else 
     sum+=a[0][i]; 
    } 
    printf("%.3f\n",sum); 
} 
getch(); 
} 

，請您提供一些提示如何優化上面的代碼。

Answer 1

沒有必要存儲整個矩陣。您可以從列j-1確定j列的值，並且，當您去替換值：

double b[2000]; 
double sum = 0; 

for (j=0; j<n; ++j) {  
    b[j]=a[j]; 
    i=j; 
    while (i>0) { 
    --i; 
    b[i] = (b[i+1]+b[i])*0.5; 
    } 
    if (i%2==1) sum += b[0]; 
} 
for (i=2; i<n; i+=2) { 
    sum += b[i]; 
} 

這應該使其更高效的內存和緩存友好的，但它不會降低複雜性。

當某些值乘以0.5時，您有一些額外的邏輯。我不確定那是基於什麼。