CSP复赛必备，时间与空间估算
一、时间估算
在竞赛环境中，一般运行程序的时间是1s。这要求我们尽量不要循环太多次数，一般情况下，建议将时间复杂度控制在10^8以内。
CCF的测评机支持10^9，在扒拉历年的代码中发现有人写过10^9的时间复杂度，而且时间只有400ms。但是不建议开到10^9，因为有可能有其他的常数干扰。
二、空间估算
变量在main函数外和main内定义变量有什么区别？
（1）生命周期不一样
（2）在main外会初始化成0，在main内不一定。
（3）在主函数外面开设一个数组，它的内存分配在数据区里；而如果在主函数内部开设一个数组，它的内存分配在栈区内。一般来说栈区的内存是比较小的，所以平常开一些小一点的数组或者变量是完全没问题的；但如果题目要求的数组或变量比较大，那就会出现爆满溢出的情况，程序将无法访问内存而出错；相反，数据区的内存较大，就不会出现这样的问题。
栈区：由操作系统自动分配释放，存放函数的参数值，局部变量的值，不需要时系统会自动清除，内存较小
堆区：由new分配的内存块，也就是说在代码中new一个数组，内存由堆区分配；堆区不由编译器管，由应用程序控制，相当于程序员控制。如果程序员没有释放掉，程序结束后，操作系统会自动回收
数据区：也称全局区或者静态区，存放全局的东西，比如全局变量，内存较大
代码区：存放执行代码的地方
2.空间估算
(1)栈内存限制
递归函数出现栈内存溢出(StackOverflow)，大部分是因为没有 return，或者在函数中开了很大的数组造成的。
栈内存通常比较有限，为几MB到几十MB。
假设使用int类型数组(每个元素4字节)，栈上最多可以分配的内存通常是1~2MB。如果栈的大小限制为2MB，数组为n×m的二维数组。需要满足：
n×m×sizeof(int) ≤ 2×1024×1024(Byte)
那么n=1000，m=500就会占用大约2MB的栈内存。
（2）总内存限制
题目中，程序运行的内存限制512MB。那么
512MB=512×1024×1024=536870912(Byte)
如果是 int 类型，也就意味着
SIZE=536870912÷4=134217728
所以如果二维数组n×m≥10⁹ ，请使用向量vector 。
3.案例
2023年CSPJ-T1 小苹果
下面这个同学的代码在洛谷是90分，但是CCF官方测评机给0分。
#include<bits/stdc++.h>
using namespace std;
long long n;
struct apple {
int num;
bool flag;
int num2;
};
apple a[100000005];
long long all,ans1=1,ans2;
bool lflag=1,used=1;
int main() {
cin>>n;
for(int i=1; i<=n; i++) {
a[i].flag=1;
a[i].num=i;//num chushi
a[i].num2=i;//num2 bianliang
}
while(1) {
int m=1;
used=1;
for(int i=1; i<=n; i++) {
if(a[i].num2%3==1) {
a[i].flag=0;
all++;
}
}
for(int j=1; j<=n; j++) {
if(a[j].flag) {
a[j].num2=m;
m++;
used=0;
}
}
if(!a[n].flag&&lflag){
ans2=ans1;
lflag=0;
}
if(used)break;
ans1++;
}
cout<<ans1<<" "<<ans2;
return 0;
}洛谷给出的最后一个点是空间超了。
而CCF官方给出的错误详情是如下：
也就是所有测试点全部超出内存限制。。。。。
这至少说明洛谷和CCF官方测评机的结果不一定一致。
如果把上面的代码中的数组少1位，改成a[10000005]，CCF官方测评机给90分
另外，把结构体拆成两个数组也可以。
那么问题的原因是什么呢？
我们来分析一下，题目限制512M，计算一下得：512*1024*1024=536870912字节，这个数如果开一维数组
#include<iostream>
using namespace std;
int a[100000000]; //1e8
int main() {
cout << sizeof(a) << endl; //400000000 (4e8)
return 0;
}如果是结构体：
#include<iostream>
using namespace std;
struct apple {
int num;
bool flag;
int num2;
};
apple a[100000005]; //1e8
int main() {
cout << sizeof(a) << endl; //1200000060 (1e9)
return 0;
}可以看出已经超了（1200000060/1024/1024=1144）
为什么，比如下面这个结构体是12字节，两个int明明是4字节，1个bool是1字节，应该是9字节，为什么输出是12字节呢。
#include<iostream>
using namespace std;
struct apple {
int num;
bool flag;
int num2;
};
apple a[1]; //1
int main() {
cout << sizeof(a) << endl; //12
return 0;
}因为结构体会字节补齐，也就是所有字节都向多字节的数据类型对齐。
比如下面这个：
#include<iostream>
using namespace std;
struct apple {
double num;
bool flag;
};
apple a[1]; //1
int main() {
cout << sizeof(a) << endl; //16
return 0;
}三、总结
循环建议10^8
一维数组建议10^8（int）（结构体需要特别注意）
二维数组建议10^5 (int)
扫描二维码推送至手机访问。
版权声明：本文由青少年编程知识记录发布，如需转载请注明出处。
