专题进阶 · 基础与数据结构推荐总顺序 · 第 23 / 148 课

按同时存活的数据量计算辅助空间,分清复制、原地修改和调用栈。

先学会这些,再进入本课 数组 递归与调用栈
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 基础与数据结构

空间复杂度Space Complexity

追踪算法额外申请的存储,区分输入、输出、辅助数组和递归栈。

建议 45 分钟 · 含手算、代码与三层练习

本课要建立的能力

按同时存活的数据量计算辅助空间,分清复制、原地修改和调用栈。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

给数组求和与反转,结果都很短,为什么程序占用的内存可能完全不同?

02一步步得到方法

先画出内存里究竟有什么

输入数组已经存在;讨论辅助空间时通常不把它再次计入。若建立 b=a[:],b 是新容器,里面即使只存引用,也需要随 n 增长的槽位。返回值是新数组时,还要说明是否把输出空间计入。

空间不是代码行数,也不是程序累计申请的总字节。我们关心执行期间同时存活的额外内存峰值;循环复用同一个临时变量,不会因为循环 n 次就变成 O(n) 空间。

把循环与递归放在一起比较

迭代求和只保留 total 和当前元素;递归求和需要让上一层等待下一层返回。深度为 n 的调用链会同时保留 n 个栈帧,即使函数正文只有三行,辅助空间仍是 O(n)。

分治递归有很多次调用也未必占 O(n) 栈:若每次折半且两个子调用顺序执行,同时等待的祖先只有 O(log n) 层。若每层还切片复制,就必须另外统计切片峰值。

沿对象的生命周期数空间

不要只数源代码里出现几个变量。把每个时刻仍然活着的数组、集合和栈帧列出来,取同时存活空间的最大值。例如连续调用两次都只保留一个长度 n 的临时数组,峰值仍是 O(n),不是把两段时间相加。

递归还要看父调用是否保留局部数据。若每层复制越来越短的数组,并在递归期间保留它们,峰值可能成为 n+(n−1)+…+1;若只传索引,情况则完全不同。

03把一个小例子完全算清楚

a=[2,4,6,8];分别迭代求和与双指针反转。

步骤计算与状态为什么这样做
开始求和total=0只增加一个累加器
遍历四次2 → 6 → 12 → 20旧 total 被覆盖,不保留四个历史值
反转第一对[8,4,6,2]交换下标 0、3
反转第二对[8,6,4,2]两指针相遇,停止

窄屏可左右滑动表格,阅读完整计算与理由。

求和结果 20;反转直接改变输入。两种实现的辅助空间都不随数组长度增长。

04为什么这个方法成立

  1. 每轮求和只需上轮累计值,不必保存所有前缀和。
  2. 反转时,区间外的元素已经在最终位置,未处理区间每次缩小两个位置。
  3. 始终只存在固定数量的标量变量,所以在通常的固定宽度数值模型下辅助空间为 O(1)。

05把推导翻译成代码

Python · 可独立运行的教学实现

def total(a):
    s = 0
    for x in a:
        s += x
    return s

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

逐个理解关键决定

s += x
覆盖已有累计值;若改为把每个累计值 append 到列表,则新增了 O(n) 输出。
left < right
中间单个元素不用交换,空数组的 right=-1 也会自然跳过。
a[left], a[right]
Python 同时赋值避免先覆盖一个值;临时保存的元素数量为常数。

06时间、空间与实现范围

求和做 n 次加法,反转做 floor(n/2) 次交换,时间都为 O(n)。

Python 大整数的位数可能增长;O(1) 辅助空间结论采用元素和累加器大小受限的常用模型。若按比特计算,要额外计入整数长度。

07改变条件,检查哪里会出错

把 a[::-1] 称为原地反转

切片会新建长度 n 的列表,应标为 O(n) 额外空间;输入修改与返回副本是不同接口。

只统计局部变量,漏掉递归栈

画出最深处同时等待的调用链,再把各层存活对象相加。

忽略语言切片是否复制

先核对容器语义;Python 列表切片会创建新列表,不能按只传边界的递归来分析。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

n=7 时原地反转交换几次?

需要一点提示

只交换对称位置。

查看解析与答案

交换 (0,6)、(1,5)、(2,4),共 3 次;位置 3 不动。

练习 2 · 边界与辨析

递归顺序计算左右两个一半,栈深是多少?

需要一点提示

关注同时存在的祖先而非总调用数。

查看解析与答案

若子问题严格折半,深度约 log₂n;无切片和大型局部数组时栈空间 O(log n)。

练习 3 · 变式与迁移

要保留原数组,又返回完整倒序数组,能承诺 O(1) 总额外空间吗?

需要一点提示

结果本身有多少槽位?

查看解析与答案

不能。输出就有 n 个位置。可以说除输出外辅助空间 O(1),但必须明确这个计数约定。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Python 官方教程 · 数据结构

理解之后,继续递进

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。