社区讨论

时间复杂度怎么分析?

P3799小 Y 拼木棒参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lo8vedhs
此快照首次捕获于
2023/10/28 01:11
2 年前
此快照最后确认于
2023/10/28 01:11
2 年前
查看原帖
有哪位大佬有空吗,能看看这段代码时间复杂度是多少?
CPP
#include<iostream>
using namespace std;
int ans=0;
void sort(int a[],int begin,int end){
    if(begin>=end){
        return;
    }
    int x=begin,y=end;
    int base=a[(begin+end)/2];
    while(x<y){
        while(a[y]>base&&y>x){
            y--;
        }
        while(a[x]<base&&y>x){
            x++;
        }
        if(x<=y){
            swap(a[x],a[y]);
            x++,y--;
        }
    }
    if(a[x]<base){
        x++;
    }
    sort(a,begin,x-1);
    sort(a,x,end);
}
void search(int res[],int res_count,int a[],int a_size,int tip){
    //cout<<"****"<<endl;
    if(res_count==4){
        sort(res,0,3);
        if(res[0]+res[1]==res[2]&&res[2]==res[3]){
            ans++;
        }
        return;
    }
    else if(tip>=a_size){
        return;
    }
    for(int i=tip;i<a_size;i++){
       // cout<<"res_count="<<res_count<<endl;
        res[res_count]=a[i];
        search(res,res_count+1,a,a_size,i+1);
    }
}
int main(){
    int n;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    sort(a,0,n-1);
    int res[4]={0};
    search(res,0,a,n,0);
    cout<<ans<<endl;
    return 0;
}

回复

0 条回复,欢迎继续交流。

正在加载回复...