一、时间估算

       在竞赛环境中，一般运行程序的时间是1s。这要求我们尽量不要循环太多次数，一般情况下，建议将时间复杂度控制在10^8以内。

      CCF的测评机支持10^9，在扒拉历年的代码中发现有人写过10^9的时间复杂度，而且时间只有400ms。但是不建议开到10^9，因为有可能有其他的常数干扰。

二、空间估算

1. 变量在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（结构体需要特别注意）

二维数组建议10^5

(adsbygoogle = window.adsbygoogle || []).push({});