时间复杂度，今天就要交了

Question

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int maxIntervalSum_1(int array[],int len)//穷举法，三层循环
{
int max=0;
for(int i=0;i<len;i++)
{
for(int j=i;j<len;j++)
{
int sum=0;
for(int k=i;k<=j;k++)
{
sum+=array[k];
}
if(sum>max) max=sum;
}
}
return max;
}
int maxIntervalSum_2(int array[],int len)//改进穷举法，两层循环
{
int max=0;
for(int i=0;i<len;i++)
{
int sum=0;
for(int j=i;j<len;j++)
{
sum+=array[j];
}
if(sum>max) max=sum;
}
return max;
}
int maxIntervalSum_3(int array[],int begin,int end)//分治法
{
int mmax=0;
if(begin=end) return array[begin]>0?array[begin]:0;
int mid=begin+(end-begin)/2;
int lmax=maxIntervalSum_3(array,begin,mid);//左半区间最大值
int rmax=maxIntervalSum_3(array,mid+1,end);//右半区间最大值
//中间区间最大值
int sum=0;
int left_max=0;
for(int i=mid;i>=begin;i--)
{
sum+=array[i];
if(sum>left_max) left_max=sum;
}
sum=0;
int right_max=0;
for(int i=mid+1;i<=end;i++)
{
sum+=array[i];
if(sum>right_max) right_max=sum;
}
mmax=left_max+right_max;
int max=(lmax>rmax)?(lmax>mmax?lmax:mmax):(rmax>mmax?rmax:mmax);
return max;
}
int maxIntervalSum_4(int array[],int len)//动态规则
{
int max=0;
int sum=0;
for(int i=0;i<len;i++)
{
sum+=array[i];
if(sum<0) sum=0;
if(sum>max) max=sum;
}
return max;
}

int main(int argc,char* argv[])
{
char* f_name=argv[1];//文件名
int n=atoi(argv[2]);//字符串转整数
int repeat_time=atoi(argv[3]);//重复次数
//读取数据到数组
FILE pf;
int data=(int*)malloc(n*sizeof(int));
if((pf=fopen("C:\text_datum.txt","r"))==NULL)
{
printf("Error\n");
system("PAUSE");
exit(1);
}
//读取文件内容到数列
for(long long int i=0;i<n;i++)
{
fscanf(pf,"%d\n",&data[i]);
}
fclose(pf);

clock_t c_start,c_end;
int maxValue=0;
c_start=clock();
for(int i=0;i<repeat_time;i++)
{
    maxValue=maxIntervalSum_1(data,n);
}
c_end=clock();
double diff_t=difftime(c_end,c_start);
printf("算法1,时间复杂度0(n^3),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);



c_start=clock();
for(int i=0;i<repeat_time;i++)
{
    maxValue=maxIntervalSum_2(data,n);
}
c_end=clock();
diff_t=difftime(c_end,c_start);
printf("算法2,时间复杂度0(n^2),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);



 c_start=clock();
for(int i=0;i<repeat_time;i++){
    maxValue=maxIntervalSum_3(data,0,n-1);
}
c_end=clock();
diff_t=difftime(c_end,c_start);
printf("算法3，时间复杂度0(nlogn),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);

 c_start=clock();
for(int i=0;i<repeat_time;i++){
    maxValue=maxIntervalSum_4(data,n);
}
c_end=clock();
diff_t=difftime(c_end,c_start);
printf("算法4，时间复杂度0(n),最大值=%d,执行时间=%f 毫秒.\n",maxValue,diff_t/repeat_time);
return 0;

}

Answer 1

先把你代码贴好