社区讨论

关于复杂度

学术版参与者 3已保存回复 6

讨论操作

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

当前回复
6 条
当前快照
1 份
快照标识符
@m32eb11t
此快照首次捕获于
2024/11/04 10:21
去年
此快照最后确认于
2025/11/04 15:25
4 个月前
查看原帖
CPP
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+5;
ll c[20][20],ans;
int cnt[27];
char a[N];
int n,m,q1[21],q2[21],t1,t2,res;
int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%d%d",&n,&m);
        int limit=(1<<m-1);
        for(int i=0;i<limit;i++){
            t1=t2=0;
            for(int j=0;j<m;j++)
            if(i&(1<<j))q1[++t1]=j;
            else q2[++t2]=j;
            ll ss=0,sa=0;
            for(int j=1;j<=t1;j++)
            for(int z=1;z<=t2;z++)
          	res++;
        }
        printf("%d\n",res);
    }
    return 0;
}
这份代码感性理解复杂度是 O(2mm2)O(2^mm^2) 的,但实测大概只跑了5e7左右,请问有没有比较严谨的复杂度证明

回复

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

正在加载回复...