# 空间复杂度
程序在定义变量、常量、数组等会占用内存空间。
```c++
int a, b, c;
char x, y;
double p, q;
```
定义了常数个基本类型变量，空间复杂度为 $O(1)$。
```c++
struct P{
int a, b, c;
}x, y, z;
```
结构体由常数个基本类型组成。定义了常数个结构体变量，空间复杂度为 $O(1)$。
```c++
int a[10];
```
数组占用了常数个整型空间，空间复杂度为 $O(1)$。
```c++
const int MAXN = 100; // MAXN 为输入数据的最大规模
int a[MAXN];
```
数组占用空间与输入规模相关，空间复杂度为 $O(n)$。
```c++
const int MAXN = 100, MAXM = 1000; // MAXN MAXM 为输入数据的最大规模
int a[n][m];
```
数组占用空间与输入规模相关，空间复杂度为 $O(nm)$。
```c++
const int MAXN = 100; // MAXN 为输入数据的最大规模
struct P{
int a[MAXN];
}b[MAXN];
```
结构体由 $1$ 个长为 $n$ 的整型数组组成。数组 $b$ 占用了 $n$ 个结构体空间，空间复杂度为 $O(n^2)$。
```cpp
const int MAXN = 1e2;
if (x % 2) {
int a;
} else {
int a[MAXN];
}
```
最坏情况下，空间复杂度为 $O(n)$。
```cpp
for (int i = 1; i <= n; i++) {
int a;
}
```
在循环中定义了一个变量，每次循环体执行完时变量 $a$ 所占内存会被释放，空间复杂度为 $O(1)$。
## 估算程序所占内存空间
我们可以根据基本类型所占用的内存空间以及数组长度来计算总的内存消耗量。
例如对于一个 $512 \text{MB}$ 空间限制的题目来说，可容纳的字节数是 $512 \times 1024 \times 1024 = 536870912$。
而我们可以根据基础数据类型的字节数来推算出程序所花费的字节数。
| 类型 | 单变量所占字节数 |
| :---------------: | :--------------: |
| char, bool | $1$ |
| int | $4$ |
| double, long long | $8$ |
```c++
int a[100005];// 4 * 100005 字节
struct P{
int a;
bool b;
int c;
}a[100005]; // (4 + 4 + 4) * 100005
//结构体会字节补齐，也就是所有字节都向多字节的数据类型对齐。
```