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

当你写代码时，程序除了输入数据本身，还需要额外的内存来存放临时变量、中间结果、调用函数的信息等。这些额外占用的内存大小，就是空间复杂度。就像你整理书包时，除了课本（输入数据）之外，还要额外拿几个文件夹、草稿本或便签纸来记录演算过程。如果这些额外东西太多，书包就装不下——程序也一样，内存有限，如果空间复杂度过高，程序可能会崩溃或者变慢。

一、空间复杂度是什么？

空间复杂度衡量的是算法运行时额外开辟的内存空间（不包括输入数据本身占用的空间）。我们通常用大O记法（比如 O(1)、O(n)）来表示它随输入规模 n 增长的趋势。

O(1)：额外空间是常数，不随输入变大而变大。
O(n)：额外空间和输入规模 n 成正比。
O(n²)：额外空间和 n² 成正比，比如二维列表。

小提示：我们只关注“额外”空间，输入数据本身不算在内，因为那是题目已经给你了的空间。

二、生活中的例子

例子1：抄写成绩单
老师让你把全班n个同学的成绩单按分数排序。

方法A：拿一张新纸（新列表），把排序后的结果抄上去。这张纸的大小和全班人数 n 一样，所以额外空间是 O(n)。
方法B：直接在原成绩单上用铅笔涂改（原地排序），顶多需要一支笔和橡皮擦，额外空间是常数 O(1)。

例子2：做数学作业

如果直接心算（只记住几个中间数），额外空间很小（O(1)）。
如果每算一步就写在草稿纸上，最后草稿纸越来越多（和题目数量 n 有关），额外空间就是 O(n)。

三、常见的空间复杂度级别

1. O(1) —— 常数空间

只用了几个变量（整数、布尔值等），不再额外分配和输入规模相关的容器。

# 原地修改列表，空间复杂度 O(1)
def square_in_place(arr):
    for i in range(len(arr)):          # i 是整数变量，常数空间
        arr[i] = arr[i] * arr[i]       # 临时计算结果也只用了一个寄存器
    return arr

nums = [1, 2, 3, 4]
square_in_place(nums)
print(nums)   # 输出 [1, 4, 9, 16]

这里没有创建新列表，只用了变量 i 和临时计算结果，额外空间和列表长度无关，所以是 O(1)。

2. O(n) —— 线性空间

创建了一个和输入规模一样大的新容器（列表、字典、字符串等）。

# 创建新列表，空间复杂度 O(n)
def square_list(arr):
    result = []          # 新列表，长度和 arr 相同
    for x in arr:        # x 是临时变量，常数空间
        result.append(x * x)
    return result

numbers = [1, 2, 3, 4]
print(square_list(numbers))   # 输出 [1, 4, 9, 16]

result 的长度等于输入数组的长度，所以额外空间是 O(n)。

3. O(n²) —— 平方空间

例如创建了一个 n×n 的二维列表（矩阵）。

# 创建 n×n 的表格，空间复杂度 O(n²)
def create_table(n):
    table = []                       # 外层列表
    for i in range(n):
        row = [i * j for j in range(n)]   # 每一行长度也是 n
        table.append(row)
    return table

t = create_table(3)
# t 是 3×3 的二维列表，共 9 个元素

4. 递归调用栈空间

递归函数每次调用自己时，系统会把当前函数的信息（参数、局部变量、返回地址等）压入一个“调用栈”。递归深度为 n 时，调用栈就需要 n 层空间，因此空间复杂度是 O(n)。

# 递归计算阶乘，空间复杂度 O(n)
def factorial(n):
    if n == 1:
        return 1
    else:
        return n * factorial(n - 1)   # 每次递归都占用一层栈空间

print(factorial(5))   # 输出 120

当 n=5 时，调用栈会依次压入 factorial(5)、factorial(4)、...、factorial(1)，共5层。如果 n=1000，栈会有1000层，可能超过 Python 的默认递归深度，导致报错。

四、新手容易犯的错误

忘记输入数据本身不算空间
有人看到列表里有 n 个元素，就说空间复杂度是 O(n)。但这是输入数据，不是“额外”空间。只有算法中新创建的那些空间才算。
忽略递归栈的空间
写递归时只想着时间复杂度，忘了递归深度也会占用 O(n) 的栈空间。
```
# 错误：以为递归是 O(1) 空间
def sum_list_recursive(arr, index):
    if index == len(arr):
        return 0
    return arr[index] + sum_list_recursive(arr, index + 1)
```
实际上递归深度等于列表长度，额外空间是 O(n)（栈空间）。

以为只有显式用 list 才算空间
有时在循环中拼接字符串或创建集合，虽然没显式写 []，但也会产生临时对象。

result = ""               # 看似只有一个字符串
for ch in "hello world":
    result = result + ch  # 每次拼接都生成新字符串，旧字符串被丢弃，但瞬间占用 O(n) 空间

这种写法临时空间也是 O(n)，不推荐。

混淆时间复杂度和空间复杂度
有时候为了省时间而多开空间（比如用字典缓存结果），这是合理的“空间换时间”。但不要以为所有优化都只考虑时间，空间也可能成为瓶颈。

五、完整可运行示例：斐波那契数列

对比递归和迭代两个版本的斐波那契数列，观察空间复杂度差异。

# 版本1：递归（空间复杂度 O(n)，因为递归栈）
def fib_recursive(n):
    """递归求斐波那契数列第 n 项，n 从 0 开始"""
    if n <= 1:
        return n
    return fib_recursive(n - 1) + fib_recursive(n - 2)

# 版本2：迭代（空间复杂度 O(1)）
def fib_iterative(n):
    """迭代求斐波那契数列第 n 项"""
    if n <= 1:
        return n
    a = 0          # 前一个数
    b = 1          # 当前数
    for i in range(2, n + 1):
        a, b = b, a + b   # 只用了两个变量，常数空间
    return b

# 测试
n = 10
print(f"递归结果: {fib_recursive(n)}")   # 输出 55
print(f"迭代结果: {fib_iterative(n)}")   # 输出 55

递归版本：虽然代码简洁，但空间复杂度 O(n)（递归深度 n），而且时间复杂度很高（O(2^n)）。
迭代版本：只用两个变量 a 和 b，空间复杂度 O(1)，效率也更高。

六、空间与时间的权衡

在算法设计中，常常需要“空间换时间”或“时间换空间”。

空间换时间：多创建一些缓存或中间结果，避免重复计算，让程序跑得更快。比如用字典记录已经算过的结果（记忆化递归）。
时间换空间：不额外开辟空间，原地修改或反复计算，但速度变慢。比如前面提到的原地排序比新建列表排序更省空间，但可能代码更复杂。

选择哪种策略取决于实际需求：如果你的程序运行在内存很小的设备（如单片机、旧手机），就要优先节省空间；如果内存足够，想快速出结果，可以多耗一点空间。

七、相关知识点指引

时间复杂度：衡量程序运行时间，和空间复杂度一起是算法效率的两个核心维度。
递归与栈：深入理解递归的空间开销。
大O记法：掌握如何用数学表达式描述复杂度。
记忆化搜索：典型的空间换时间应用。

希望这篇文章能帮你清晰理解空间复杂度，下次写代码时记得评估一下自己占了多少额外内存！

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