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为什么这个方法成立
- 每轮求和只需上轮累计值,不必保存所有前缀和。
- 反转时,区间外的元素已经在最终位置,未处理区间每次缩小两个位置。
- 始终只存在固定数量的标量变量,所以在通常的固定宽度数值模型下辅助空间为 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从手算到独立迁移
先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。
n=7 时原地反转交换几次?
需要一点提示
只交换对称位置。
查看解析与答案
交换 (0,6)、(1,5)、(2,4),共 3 次;位置 3 不动。
递归顺序计算左右两个一半,栈深是多少?
需要一点提示
关注同时存在的祖先而非总调用数。
查看解析与答案
若子问题严格折半,深度约 log₂n;无切片和大型局部数组时栈空间 O(log n)。
要保留原数组,又返回完整倒序数组,能承诺 O(1) 总额外空间吗?
需要一点提示
结果本身有多少槽位?
查看解析与答案
不能。输出就有 n 个位置。可以说除输出外辅助空间 O(1),但必须明确这个计数约定。