时间复杂度,求解答,求解答


#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;
}

img


求告知该怎么办?
这是文件链接
https://share.weiyun.com/FF6MWRaQ

img

=换成==

img

你这么写不是要从命令行获取数据吗?

img


你都没有传入参数,你可以先试试把值写死试试,比如这样:

int n = 4;  //字符串转整数
int repeat_time = 3;//重复次数

修改如下,供参考:

#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)  //(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[])
{
    int n = 0,repeat_time = 3;//重复次数
    FILE *pf;
    if (argc >= 4){    //命令行模式
        //char* f_name=argv[1];//文件名 字符串不能赋值,需拷贝
        if((pf=fopen(argv[1],"r"))==NULL){
            printf("Error\n");
            system("PAUSE");
            exit(1);
        }
        n = atoi(argv[2]);      //字符串转整数
        repeat_time = atoi(argv[3]);//重复次数
    }
    else{
        if((pf=fopen("D:\\text_datum.txt","r"))==NULL){
            printf("Error\n");
            system("PAUSE");
            exit(1);
        }
        int tmp;
        while (1){
            if (fscanf(pf,"%d",&tmp) != 1) break;
            n++;
        }
        rewind(pf);
    }
    //printf("n=%d,repeat_time=%d\n",n,repeat_time);
    //读取文件内容到数列
    //读取数据到数组
    int* data=(int*)malloc(n*sizeof(int));
    for(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;
}

命令行模式,是模拟dos命令行的情况下运行,如下图,供参考:

img