Hello 算法 2.4 精讲：空间复杂度，数清同时活着的数据与调用状态

主线：不是一共创建过多少，而是最多同时需要多少

空间复杂度描述：在明确统计边界和存储模型后，运行期间最多同时需要保留的空间，如何随输入规模增长。先问“算哪些空间”，再问“什么时候达到峰值”，最后判断增长阶。

原书 2.4 包含算法相关空间、推算方法、常数/线性/平方/指数/对数五类增长，以及时间与空间的权衡。本文沿这些主题重新组织，加入原创 Python 示例、执行状态表、反例和测量实验；不把代码行数、变量名数量或累计分配量当作峰值空间。

章节复盘：2.5 小结：把执行次数、存活状态与工程选择连起来。

知识点 01—03：输入、辅助状态、输出，要先划清边界

原书默认排除输入，把暂存和输出都计入空间。其他资料说 auxiliary space 时常排除输入和输出。本文同时写清“辅助空间”和“计入新输出后的空间”，避免两个正确答案看起来互相矛盾。

已经存在的列表仅被传入函数，并不再次创建一份输入。如果答案直接返回原对象的引用，也没有因此新建 n 个元素。输入与输出可以指向同一个对象，不能按角色标签把同一块存储重复相加。反过来，复制输入得到的新列表，必须计入新分配的空间。

默认 n 是有限普通列表的长度，或明确声明的非负规模。采用常用机器字/引用计数模型：固定大小数值、索引和引用按单位空间；Python 任意长整数、对象头、容器容量、解释器和分配器另作说明，不假定每个变量恰好占固定字节。

知识点 04：多一个变量名，不一定多一份数据

赋值 alias=original 只建立另一个绑定；浅复制 original.copy() 创建新的外层列表，却仍引用原来的内层列表；deepcopy 则按规则递归复制对象，并用备忘机制处理共享与循环，不是“无脑复制一切”。

下面先修改浅复制所共享的内层列表，原对象也随之改变；深复制的内层列表不受影响。三个对象身份判断依次为 True、False、True，分别表示共享原外层、新建外层、共享原内层。

空间分析应跟踪实际对象及引用关系，而不是数变量名。若有 n 个引用指向同一个大对象，引用槽位需要 Θ(n)，但大对象的实体只算一次。深复制的成本取决于对象图，不存在适用于任意对象的简单“列表长度乘一个固定字节”公式。

依据：Python copy：绑定、浅复制与深复制。

from copy import deepcopy

original = [[1], [2]]
alias = original
shallow = original.copy()
deep = deepcopy(original)
print(alias is original, shallow is original, shallow[0] is original[0])
shallow[0].append(9)
print(original)
print(deep)

知识点 05：原地处理与新建输出，是两份不同的空间账

下面的 reverse_in_place 在同一个列表上交换两端元素，额外只有两个索引和交换时的少量临时引用；辅助空间为 Θ(1)。它明确允许修改输入，返回 None。切片版返回一个新的逆序列表，新输出包含 n 个引用槽位；输出为 Θ(n)，辅助控制状态仍是常数量。

如果任务要求保留输入，不能只说“原地更省空间”就擅自改写它；先复制再原地处理，仍需要 Θ(n) 新空间。“原地”描述修改位置，某些原地算法也可能另有递归栈或工作区，不能不看实现就一律判 O(1)。

def reverse_in_place(values):
    left, right = 0, len(values) - 1
    while left < right:
        values[left], values[right] = values[right], values[left]
        left += 1
        right -= 1

values = [1, 2, 3, 4]
result = reverse_in_place(values)
print(values, result)
source = [1, 2, 3, 4]
copied = source[::-1]
print(source, copied, copied is source)

知识点 06—07：累计创建是求和，同时保留才构成峰值

假设依次复制长度 1、2、3、4 的前缀。累计复制了 10 个元素位置；若每轮用完就丢弃引用，最多只需要一个长度 4 的前缀。若把所有前缀留在 retained 中，它们同时活着，峰值就变成 1+2+3+4=10 个位置。

下面的计数器仅跟踪新前缀内部引用槽位，不包含原输入、外层 retained、容器头或计数器自身，不能称为实测字节。del prefix 明确移除本轮局部引用；不保留时没有上轮前缀与下轮复制重叠。全部保留时移除局部引用不会删掉 retained 中的引用。

两种方案累计复制都为 n(n+1)/2，因此都有平方级复制工作；但前缀数据的峰值分别为 Θ(n) 与 Θ(n²)。这正是时间累计与空间峰值不能混算的原因。实际运行时的回收、空闲内存复用和 RSS 可能不同，后面单独说明。

def prefix_storage_profile(values, keep):
    retained = []
    allocated_slots = 0
    live_slots = 0
    peak_slots = 0
    for stop in range(1, len(values) + 1):
        prefix = values[:stop]
        allocated_slots += len(prefix)
        live_slots += len(prefix)
        peak_slots = max(peak_slots, live_slots)
        if keep:
            retained.append(prefix)
        else:
            live_slots -= len(prefix)
        del prefix
    return allocated_slots, peak_slots

for keep in (False, True):
    print(keep, prefix_storage_profile([0, 1, 2, 3], keep))

知识点 08：离开一轮循环，不会自动清掉所有 Python 状态

Python 的 for 和 if 通常不建立独立的函数局部作用域；循环变量在循环结束后仍可能绑定最后一个对象。对象是否继续占用空间，要看后面是否仍有引用，而不是看它是否写在缩进块里。

这里补足原书“每轮变量会被释放”的教学简化：若循环把对象追加到列表、放进全局缓存、保留到生成器局部状态、被闭包或异常回溯引用，它就可能继续存活。即使局部名被重新绑定，其他引用也不会跟着消失。

del name 移除的是该名称绑定，不是命令运行时立即把全部相关字节返还操作系统。常规 CPython 引用计数常能及时释放不再引用的非循环对象，但 Python 语言不承诺所有实现都在同一时刻回收；内存分配器还可能保留空闲块。分析中的“所需存活空间”与进程监控读数要区分。

依据：Python 数据模型：对象与回收。

知识点 09—10：常量大小缓冲区与随 n 增长的容器

固定创建 10,000 个引用槽位，虽然可能占不少内存，相对 n 仍为 Θ(1)；创建 n 个槽位是 Θ(n)。“常数空间”不代表零内存，也不意味着绝对更小：某个大固定缓冲区，在小输入时完全可能更大。

辅助状态逐轮复用，且不保存历史时，执行 n 次并不要求 n 份状态同时存在。反之，即使只用一个变量名 values，把它绑定到 [0]*n，容器仍有 n 个槽位；“只有一个变量”不能证明 O(1)。

本节使用普通 Python 列表的引用模型：列表保存的是元素引用，元素对象可能共享；其预留容量、对象头和引用宽度影响实际字节，但不会把长度 n 的引用容器变成常数空间。

知识点 11：二维外形不保证真有 n² 个独立位置

正确构造 n×n 独立行列表时，有 n 个外层引用、n 个行对象和 n² 个行内引用槽位，因此新结果空间为 Θ(n²)（n 增长时）。如果行列不同，应写 Θ(rows·columns+rows)，不能未经关系假设都简化成平方。

[[0]*n]*n 却把同一行引用重复 n 次：不是 n 行独立数据。它只有一份长度 n 的内层列表，加上长度 n 的外层列表；在这个示例里，引用存储为 Θ(n)。代价不是“聪明地压缩独立矩阵”，而是改变了语义：修改一个格子会影响每一行同一列。

下面的 id 用来比较当前存活对象的身份，具体 ID 值不展示、不保存。bad 只有 1 个不同的行对象，good 有 3 个。sum(len(row) for row in bad) 虽为 9，却把共享行重复遍历，不能当成物理分配了 9 个不同槽位。

n = 3
bad = [[0] * n] * n
good = [[0] * n for _ in range(n)]
bad[0][0] = 7
good[0][0] = 7
print(bad)
print(good)
print(len({id(row) for row in bad}), len({id(row) for row in good}))

知识点 12—13：递归总调用数与同时未返回的调用数

一条递减到 0 的调用链，进入 n、n−1、…、0 时，上层调用都还没结束，因此峰值有 n+1 个该递归函数的活跃调用。每帧只含常量级状态时，辅助空间 Θ(n)。普通循环逐次调用并等待子函数返回，不会自动叠起 n 层这样的调用链。

如果每次递减 1 还分两支，总调用数可达到 2ⁿ⁺¹−1；但普通同步执行先完成左分支再执行右分支，峰值链仍只有 n+1 层。没有把全部递归树节点实体保存下来时，不能把总调用数当作栈空间。

下面真实执行两种递归，用 active 在进入/退出时加减，peak 记录峰值。计数不包含外层包装函数、解释器已有调用或每帧实际字节；输出是调用次数、递归函数峰值活跃数、结束后活跃数。finally 保证退出时记录回落。

def call_profile(n, branching=False):
    if type(n) is not int:
        raise TypeError("n must be an integer")
    if n < 0:
        raise ValueError("n must be nonnegative")
    calls = active = peak = 0
    def visit(remaining):
        nonlocal calls, active, peak
        calls += 1
        active += 1
        peak = max(peak, active)
        try:
            if remaining > 0:
                visit(remaining - 1)
                if branching:
                    visit(remaining - 1)
        finally:
            active -= 1
    visit(n)
    return calls, peak, active

for n in (0, 1, 3):
    print(n, call_profile(n), call_profile(n, branching=True))

知识点 14：深度 n 也可能保留平方量级的数据

“深度乘常量帧大小”要求每帧只保留常量状态。如果第 1 帧保留长度 n 的列表，第 2 帧保留 n−1 个位置，一直到长度 1，在深入到基本情况时它们都还在，合计 n(n+1)/2 个位置，形成 Θ(n²) 辅助空间；栈控制状态的 Θ(n) 反而不是主导项。

下面每层 block 都属于这次调用，在子调用返回后还要读取它，因此必须保留。计数器只统计这些 block 的长度，不声称是完整内存字节。n=4 的峰值是 4+3+2+1=10；n=0 没有 block，但仍存在基本调用和固定控制状态。

这里的“平均长度”精确为 (n+1)/2，不是 n/2；两者同阶，但精确求和与渐近结论要分别表述。也可以复用 调用局部状态的既有笔记理解为何每层有自己的 block。

def held_list_profile(n):
    if type(n) is not int:
        raise TypeError("n must be an integer")
    if n < 0:
        raise ValueError("n must be nonnegative")
    live = peak = 0
    def visit(size):
        nonlocal live, peak
        if size == 0:
            return
        block = [None] * size
        live += len(block)
        peak = max(peak, live)
        try:
            visit(size - 1)
            assert len(block) == size
        finally:
            live -= len(block)
    visit(n)
    return peak, live

for n in (0, 1, 4):
    print(n, held_list_profile(n))

知识点 15：减半递归的对数栈，不等于整个算法都对数空间

下面每次把规模整除 2，只继续一个子问题，每层只保留固定数量的控制状态。n≥1 时，递归调用深度为 ⌊log₂n⌋+1，所以栈状态为 Θ(log n)（讨论 n 增长时）；n=0 或 1 都只有一个基本调用。改写成 while 并复用状态，可以省去这份递归链。

归并排序也常有 Θ(log n) 递归栈，但合并还可能需要 Θ(n) 的额外数组，总辅助空间便由数组主导。“栈高是对数”只说明一项账，不能直接宣布总空间是对数。如果递归时还做切片，也要计入仍被上层保留的切片对象。

CPython 不为普通 Python 函数做尾递归消除；把返回语句改成尾递归形式，并不能自动把线性帧数变常数。深递归还可能触发 RecursionError，本节只运行小深度验证，不修改解释器递归限制。详见尾递归与优化边界。

def halving_depth(n):
    if type(n) is not int:
        raise TypeError("n must be an integer")
    if n < 0:
        raise ValueError("n must be nonnegative")
    if n <= 1:
        return 1
    return 1 + halving_depth(n // 2)

for n in (0, 1, 2, 3, 16):
    print(n, halving_depth(n))

知识点 16：保存整棵树，和只沿树执行，是两回事

如果真的构造并返回一棵每层完全展开的二叉树，所有节点都由根间接引用，构造结束后仍需保留。以 levels 表示非空层数，节点数为 1+2+…+2^levels−1=2^levels−1，因此新输出为 Θ(2^levels)；构造递归的控制栈仅 Θ(levels)，但计入输出后的空间由节点实体主导。

下面 levels=0 返回 None；levels=3 的输出含 7 个不同节点。这里规模参数是层数；如果改以输出节点总数 N 为规模，同一输出占 Θ(N)，而不叫“相对 N 的指数空间”。没有保存节点的分支递归则不同，前面的 call_profile 已展示其线性峰值链。

count_nodes 只是为核对建树结果而另外运行的遍历，不属于 build_tree 本身；不能把验证步骤的空间混进构造接口的分析。本节只展示最多 4 层，验证也限制小规模，不尝试建立巨树。

class Node:
    __slots__ = ("left", "right")
    def __init__(self, left, right):
        self.left = left
        self.right = right

def build_tree(levels):
    if type(levels) is not int:
        raise TypeError("levels must be an integer")
    if levels < 0:
        raise ValueError("levels must be nonnegative")
    if levels == 0:
        return None
    return Node(build_tree(levels - 1), build_tree(levels - 1))

def count_nodes(root):
    if root is None:
        return 0
    return 1 + count_nodes(root.left) + count_nodes(root.right)

for levels in range(5):
    print(levels, count_nodes(build_tree(levels)))

知识点 17：生成器不一次返回全部，不等于它一定省空间

stream_rows 每次生成一个单元素列表。消费完就丢弃、且消费者不积累历史时，当前行与生成器控制状态可按 Θ(1) 工作空间处理；若用 list(stream_rows(n)) 全部接住，结果保存 n 行，输出仍为 Θ(n)。输入若本来就是大列表，其输入空间也不会因换成生成器而消失。

buffered_rows 则先创建长度 n 的 buffer，再逐项 yield。即使当前只取出一个值，暂停的生成器仍保留 buffer 及其局部状态，额外空间仍是 Θ(n)。是否逐项产出，与内部是否预先物化数据，是不同的问题。

单次 yield 也可能产出大对象；生成器还可能通过闭包或局部引用保留源数据。要沿引用关系检查。下面 close() 让暂停的生成器结束，避免示例继续保留缓冲区；它不保证 RSS 立即下降。

依据：Python yield：暂停时保留局部状态。

def stream_rows(n):
    for index in range(n):
        yield [index]

def buffered_rows(n):
    buffer = [0] * n
    for value in buffer:
        yield value

streamed_total = 0
for row in stream_rows(4):
    streamed_total += row[0]
print(streamed_total)
print(list(stream_rows(4)))
pending = buffered_rows(4)
print(next(pending))
pending.close()

五种空间增长：必须连同统计范围一起读

此表给出同阶增长，不是某台机器的字节公式。正整数 N 的十进制结果长度为 ⌊log₁₀N⌋+1，相对数值 N 属于对数长度；相对它自己的表示位数，则是线性长度。不要在更换规模定义后仍沿用原复杂度名词。O 与 Θ 的区别见2.3 的增长边界。

知识点 18：getsizeof 不是递归计算整棵对象图

sys.getsizeof 返回直接归属于对象的字节，不会自动把它引用的全部对象递归相加。下面两个外层列表都只有一个元素引用，但内层 bytearray 的数据长度差很多。在本节验证环境中，外层列表直接大小相同；这不说明它们连同内容的总占用相同，也不是跨实现固定字节保证。

如果手工遍历对象图统计大小，需要考虑共享对象和循环，避免同一对象重复加账或无限递归；还应声明是否把输入对象、共享全局常量和解释器内部状态纳入统计。对复杂原生扩展，仅靠这个函数也可能看不到完整设备或外部分配。

依据：sys.getsizeof 的直接归属范围。

from sys import getsizeof

small = [bytearray(8)]
large = [bytearray(8192)]
print(len(small), len(large))
print(getsizeof(small) == getsizeof(large))
print(len(small[0]), len(large[0]))

知识点 19：把当前存活量与过程峰值分开测

下面在独立脚本中运行。transient 创建 bytearray 后只返回长度，缓冲区可在函数结束后释放；retained 返回缓冲区对象，调用方用 result 继续保留它。每种模式、每个 n 都重新开始追踪，共运行三轮；导入和函数定义在追踪开始前完成。

get_traced_memory() 的 current 是此刻仍被追踪的内存块字节，peak 是本次追踪区间的最高值。它追踪 Python 分配器覆盖的内存块，不是整个进程 RSS，不包含开始追踪前的全部历史对象，也不自动覆盖所有原生库或设备内存。GC、tracemalloc 自身和其他运行条件也会影响测量。

实验在读取 current/peak 后才构造 JSON 输出并打印，避免把输出格式化混入这次读数。数据 n 以字节为单位，三轮结果只作环境内观察，不建立“必须恰好几个字节”的性能通过门槛。更完整的工具范围也见 2.1 内存实验。

import gc
import json
import platform
import tracemalloc

def transient(n):
    buffer = bytearray(n)
    return len(buffer)

def retained(n):
    return bytearray(n)

print(json.dumps({"python": platform.python_version(),
                  "implementation": platform.python_implementation()}))
for round_index in range(3):
    for n in (0, 1024, 8192):
        for name, function in (("transient", transient), ("retained", retained)):
            gc.collect()
            tracemalloc.start()
            result = function(n)
            current_bytes, peak_bytes = tracemalloc.get_traced_memory()
            tracemalloc.stop()
            result_size = result if name == "transient" else len(result)
            print(json.dumps({"round": round_index, "n": n, "mode": name,
                              "result_size": result_size,
                              "current_bytes": current_bytes,
                              "peak_bytes": peak_bytes}))
            del result

实验记录：字节读数只支持这个环境中的这次观察

2026-10-17 在 CPython 3.12.14 中实际运行上述原样脚本，每个规模/模式各测三轮；共 18 条观察。下表为三轮最小值—最大值，单位为字节，不是通用常数。

本次 transient 在返回长度后，缓冲区不再由 result 保留，当前追踪值较小；过程峰值仍包含它。retained 的 result 继续持有缓冲区，因此读取时仍保留该分配。n=0 也可能分配对象头，返回整数等其他分配也可能被追踪，不能简单把每个读数都解释成 n。

读数只支持这个环境、这次输入与这个追踪区间的观察；其他实现、版本和分配器可能不同。没有以某个固定字节值或大小排序作为正确性断言，也不把 tracemalloc 的结果当作 RSS。完整逐轮数据、代码摘要与结构验证记录随站点源码保留，便于重跑。

知识点 20：以空间换时间，有时总空间阶数却看不出差别

下面两种去重都要求保留第一次出现的顺序，不修改输入，只处理普通整数。slow_unique 在已经构建的结果里逐次找值；fast_unique 另外维护 seen 集合，通常减少查找工作。

k≤n 是不同值数量，+1 保留空输入时的固定控制开销。总空间同阶，不代表真实字节相同；新增索引仍有成本。集合查找的期望条件不能改成无条件最坏 O(1)。如果值不可哈希，需要改规格或实现，不能直接套本例。

是否值得用缓存、索引或预计算，应根据查询频率、更新成本、内存上限和失效规则选择。空间换时间不是唯一优化方式：消除不必要复制、共享只读数据或减少重复计算，也可能同时改善时间和空间。

def slow_unique(values):
    result = []
    for value in values:
        if value not in result:
            result.append(value)
    return result

def fast_unique(values):
    result = []
    seen = set()
    for value in values:
        if value not in seen:
            seen.add(value)
            result.append(value)
    return result

values = [3, 1, 3, 2, 1]
print(slow_unique(values))
print(fast_unique(values))
print(values)

空间分析复查：先画生存区间，再找主导状态

1. 定义规模与统计口径：n 是元素数、层数还是数值？是否计输入、输出和递归栈？
2. 列出新对象：是新数据、别名、浅复制，还是内部共享？实际新增多少引用和实体？
3. 追踪生存区间：什么时候创建，谁继续引用，什么时候不再需要？多个缓冲区会不会重叠？
4. 递归逐帧展开：只保存索引，还是每帧还持有数组、切片或缓存？两个子调用是否顺序执行？
5. 沿时间找峰值：同一时刻存在的状态相加；不把历史累计申请直接当峰值。
6. 区分数学和测量：槽位/节点/帧计数、tracemalloc 字节、getsizeof、RSS 各代表不同范围。

“最坏输入”与“执行过程峰值”也是两个维度：固定 n 后可以对合法输入选最坏情况，再对该次执行找时间上的峰值。仅比较 n<10 与 n>10 的分支，首先是在比较不同规模，不应混成同一规模的输入分布分析。n=10 的边界也必须按实际条件处理。

本节复盘：10 道建议题与参考答案

1. 输入、输出指向同一列表时，为什么不能按两份独立存储相加？
2. alias=values 与 values.copy()，新建了哪些对象？
3. 依次复制长度 1…n 的前缀，累计复制与及时丢弃后的峰值分别是多少？
4. 为什么 [[0]*3]*3 不能当作 3 个独立行？
5. 每次减 1 的两分支递归，总调用数指数增长，为什么栈深度仍线性？
6. 每层保留长度 n、n−1、…、1 的列表，峰值如何计算？
7. 归并排序的调用链是对数，能否直接说总辅助空间为对数？
8. 生成器每次只 yield 一个值，为什么也可能持有线性数据？
9. getsizeof 外层列表大小相同，是否说明总对象图大小相同？
10. 函数返回后 current 很小，是否说明执行过程不占多少空间？

题目属于作者建议，未新增用户讨论事件，未标记你已掌握或已复盘。建议先手画“对象—引用—存活阶段”，再运行小输入核对。

来源、改动说明与后续顺序

主题依据：krahets / 《Hello 算法》2.4 空间复杂度，2026-10-17 核对，覆盖 2.4.1—2.4.4。本文重新组织概念，加入原创代码、对象关系、存活区间、峰值计数、Python 实验及练习；补充输出统计口径、共享引用、Python 回收时机、生成器状态，并澄清只分析栈高不等于分析算法全部空间。

相关改编文字采用 CC BY-NC-SA 4.0，保留署名、来源及改动说明，遵守非商业与相同方式共享；不更改本站其他内容或源码许可。Python 行为依据官方 copy、数据模型、yield、sys、tracemalloc及尾调用解释器与 Python 函数优化的区别。

继续阅读 2.5 复杂度分析小结，将时间、空间与递归串起来；下一节为 2.6 练习，再进入第 3 章。正文第 1—15 章完成后再补前言和附录。发布进度与个人学习、讨论及复盘进度分别记录，以覆盖表为准。