下面的两个程序从文件中获取n个整数,并计算第a到第b个整数的和q(问题数量)次。我认为上面的程序时间复杂度比下面的差,但我在计算这两个算法的时间复杂度时遇到了问题。
下面的程序获取1到m之间的n个整数并对它们进行排序。但是,我无法计算时间复杂度。
[input sample]
5 3
5 4 3 2 1
2 3
3 4
2 4
[output sample]
7
5
9
程序 1:
#include <stdio.h>
FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");
int n,q,a,b,sum;
int data[1000];
int main()
int i,j;
fscanf(in,"%d%d",&n,&q);
for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]);
for i=0;i<q;i++)
{
fscanf(in,"%d%d",&a,&b);
sum=0;
for(j=a;j<=b;j++) sum+=data[j];
fprintf(out,"%d\n",sum);
}
return 0;
}
程序2:
#include <stdio.h>
FILE *in=fopen("input.txt","r");
FILE *out=fopen("output.txt","w");
int n,q,a,b;
int data[1000];
int sum[1000];
int main()
{
int i,j;
fscanf(in,"%d%d",&n,&q);
for(i=1;i<=n;i++) fscanf(in,"%d",&data[i]);
for(i=1;i<=n;i++) sum[i]=sum[i-1]+data[i];
for(i=0;i<q;i++)
{
fscanf(in,"%d%d",&a,&b);
fprintf(out,"%d\n",sum[b]-sum[a-1]);
}
return 0;
}
下面的程序获取1到m之间的n个整数并对它们进行排序。但是,我无法计算时间复杂度。
[input sample]
5 5
2 1 3 4 5
[output sample]
1 2 3 4 5
程序:
#include <stdio.h>
FILE *in=fopen("input.txt","r")
FILE *out=fopen("output.txt","w")
int n,m;
int data[1000];
int count[1000];
int main()
{
int i,j;
fscanf(in,"%d%d",&n,&m);
for(i=0;i<n;i++)
{
fscanf(in,"%d",&data[i]);
count[data[i]]++
}
for(i=1;i<=m;i++)
{
for(j=0;j<count[i];j++) fprintf(out,"%d ",i);
}
return 0;
}
有讽刺意味(或者说并不讽刺)的是,我无法计算自己算法的时间复杂度,但我很热衷于学习,所以请编程大神们帮帮我!