我有一个 N*N
上三角矩阵,其属性为,它的所有对角线元素都是 a1,a2,a3,...,aN
。我想要 a[i][j] (对于所有 j>i)
应该是
(a[i][j-1] + a[i+1][j]) / 2.
我有很多测试用例,每次都必须应用这个属性来计算答案。执行此操作的最佳方法是什么,以便所有测试用例的总体运行时间都更少?测试用例:输入为 N 和 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();
}
请提供一些如何优化上述代码的提示。
最佳答案
没有必要存储整个矩阵。您可以从第 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 时,您有一些额外的逻辑。我不确定这是基于什么。
关于c - 如何提高C中矩阵运算的效率?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12759708/