C에서 행렬 연산의 효율성을 높이려면?

Question

나는 모든 대각선 요소가 a1,a2,a3,...,aN 인 속성을 가진 N*N 위 삼각 행렬을 가지고 있습니다. 나는 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를 곱한 경우에 대한 추가 논리가 있습니다. 나는 그것이 무엇을 기초로하는지 확신하지 못한다.