时间复杂度&&空间复杂度

时间复杂度：计算原子操作多少次（一般关心最坏情况下）

有些时候也可以计算平均复杂度

时间复杂度与输入的一些大小（变量）相关

用O()记录，比如O（n*n),O(2^n)

其中n是数据规模

计算保留最大计算量的值，例如2n+2n*n+2*n*n保留n*n（包括舍去常数）

数据规模变量数量大于2，每个单独计算加起来就行了，例如O(n*m+k*l);

特别的：O（1）被称为常数复杂度（与数据规模范围无关）

一般粗略计算原子操作数量，我们认为一秒钟电脑能1亿次原子操作

出一组极限数据试一试

有些时候，我们可以通过数据规模来揣摩复杂度的考察

空间复杂度

也用大O，表示内存占用

粗略计算之后还要计算实际运用的空间

1GB=1024MB

1MB=1024KB

1kB=1024B

1B=8bit

c++：sizeof()

#include<iostream>
#include<cmath> 
using namespace std;
int shuzu[33500000];
int main(){
	cout<<sizeof(shuzu)/1024./1024.<<endl;
	cout<<sqrt(33500000)<<endl;
	//这样就能算出占用多少mb了
	//基本存储单位位字节(1B),1B=8b 
	//一般比赛128mb最大 
	//一维int数组最多开3350万左右
	//二维数组int最多开 5700左右 
	return 0;
}