空间复杂度：程序占多少内存？

空间复杂度：你的程序“吃”多少内存？

你有没有玩过搭积木？每搭一层就需要一块积木。如果让你搭一个N层高的塔，你就需要N块积木。这些积木就是程序运行时“占用的空间”。在计算机里，空间指的是内存。空间复杂度就是：当数据量增大时，程序要额外用多少内存。写代码时，我们不仅要让程序跑得快（时间少），还要让程序占内存少（空间小）。

空间复杂度是什么？

简单说，空间复杂度表示程序运行需要占用的内存大小，它和数据量N的关系。我们常用大O符号表示，比如O(1)、O(N)、O(N²)等。

O(1)：无论数据量多大，占用的内存是固定不变的。比如只用一个变量存数字。
O(N)：数据量增大N倍，占用的内存也增大N倍。比如用一个长度为N的数组。
O(N²)：数据量增大N倍，占用的内存增大N²倍，比如一个N×N的二维数组。

生活中的比喻：你去图书馆看书，但只能带一个书包。如果只看1本书，书包里放1本就行；要看100本书，书包里就得放100本（当然放不下，这里只是比喻）。这个书包的“容量”就是空间复杂度。如果书包只能放下固定数量的书（比如5本），那就是O(1)；如果书包大到能装下所有要看的书，那就是O(N)。

另一个例子：存零花钱。如果你把每笔零花钱都记在一个小本子上（每个记录占一行），有N笔钱就需要N行空间，这是O(N)。如果你只记总额（用一个变量），不管多少笔都只占一行，这是O(1)。

空间复杂度的常见表示

O(1)：常数空间。例如：

int main() {
    int N;          // 数字个数（一个变量）
    cin >> N;
    int sum = 0;    // 求和结果（一个变量）
    for (int i = 0; i < N; i++) {
        int x;      // 每次只用一个临时变量
        cin >> x;
        sum += x;
    }
    cout << sum << endl;
    return 0;
}

无论N多大，程序只用少数几个变量（N, sum, i, x），空间不变，所以是O(1)。

O(N)：线性空间。例如：

#include <iostream>
using namespace std;
int main() {
    int N;
    cin >> N;                // 输入数字个数
    int arr[N];              // 申请N个int的空间
    for (int i = 0; i < N; i++) {
        cin >> arr[i];       // 把数字放进数组
    }
    // 打印第一个数
    cout << arr[0] << endl;
    return 0;
}

如果输入N=1000，arr会占用1000个int的大小（约4KB）。如果N=1000000，就占约4MB。空间和N成正比，所以是O(N)。

O(N²)：平方空间。比如一个N×N的二维数组，当N=100时，有10000个元素，占用约40KB（每个int 4字节）。当N=1000时，有1百万个元素，占用4MB。N增大10倍，空间增大100倍。

常见错误（新手容易犯）

定义超大数组：比如写 int big[10000000]; 但程序只需要处理几百个数。这会导致内存浪费，甚至程序崩溃（栈溢出）。应该按需定义大小，或者用动态数组（如vector）。
忘记数组越界：数组大小是N，但循环写到N+1，虽然可能不报错，但访问了不属于自己的内存，可能导致程序异常或数据被修改。空间复杂度分析时，访问越界不算占用更多空间，但那是错误的行为。
混淆时间与空间：有时为了一点点时间优化，定义了一个巨大的二维数组，却只用了一小部分。比如用一个1000×1000的数组存10个数，浪费了999990个格子。合理的做法是用小数组或者列表。
递归导致栈空间爆炸：递归函数每次调用都会在内存中“栈”上分配空间（保存参数、局部变量等）。如果递归深度达到N（比如N=100000），会占用大量栈空间导致溢出。此时可能需要用循环替代递归，或者改用堆内存（比如动态数组）。

空间和时间要平衡

有时候，多用一点空间可以换来运行速度的提升。比如把已经算过的结果存起来，下次直接拿来用，就不必再算一遍。这叫做空间换时间。

生活中的例子：你要计算全班50个人的数学成绩总和。如果每次求总和都从头加一遍，时间O(N)；但如果提前把每个同学的成绩都记下来（占用数组空间O(N)），那么第二次只需要直接加一次，时间O(1)。或者更常见的是用备忘录：比如你每天要帮妈妈记家里买了什么菜，如果每次买完菜都记在本子上（花时间），以后查起来方便（省时间）；如果每次都口头记住（省空间），但容易忘（花时间再问一遍）。

代码中经典例子是斐波那契数列：

普通递归：时间O(2^N)，空间O(N)（递归栈），非常慢。
用数组存结果（动态规划）：时间O(N)，空间O(N)，快很多。
进一步优化：只用两个变量迭代，时间O(N)，空间O(1)，又快又省。

写程序时，要根据实际需求权衡。比如手机内存小，就要省着用；而服务器内存大，可以多用空间换速度。

完整示例：计算平均值（对比两种空间）

下面我们写两个版本的程序，都用来计算用户输入的N个数的平均值。第一个版本用数组，空间O(N)；第二个版本不用数组，只用变量边读边算，空间O(1)。

版本1：用数组（空间O(N)）

#include <iostream>
using namespace std;
int main() {
    int N;
    cin >> N;                    // 输入数字个数
    int scores[N];               // 数组，占N个int空间
    int sum = 0;                 // 累加和
    for (int i = 0; i < N; i++) {
        cin >> scores[i];        // 把数字存到数组里
        sum += scores[i];        // 同时累加
    }
    double average = (double)sum / N;   // 计算平均值
    cout << "平均分: " << average << endl;
    // 这里还可以再次访问scores数组，比如找出最高分
    int maxScore = scores[0];
    for (int i = 1; i < N; i++) {
        if (scores[i] > maxScore) maxScore = scores[i];
    }
    cout << "最高分: " << maxScore << endl;
    return 0;
}

版本2：不用数组（空间O(1)）

#include <iostream>
using namespace std;
int main() {
    int N;
    cin >> N;                    // 输入数字个数
    int sum = 0;                 // 累加和
    int x;                       // 临时存每个数字
    for (int i = 0; i < N; i++) {
        cin >> x;                // 读一个数字，不存到数组
        sum += x;                // 直接累加
    }
    double average = (double)sum / N;
    cout << "平均分: " << average << endl;
    // 注意：版本2无法再查找最高分，因为数字已经丢弃
    return 0;
}

两个程序输出的平均值相同。版本1占用了N个int的空间（比如N=10000时约40KB），版本2只用了几个变量（固定约几十字节）。但版本1可以后续访问每个数字（比如找最高分、排序等），版本2不能。所以选择哪种取决于需求：如果只需要平均值，用版本2省空间；如果需要重复使用数据，则用版本1。