数据结构与算法 / 系统课时
空间复杂度的基本概念
空间复杂度的基本概念
学习目标
- 理解空间复杂度描述额外内存随输入规模增长的趋势。
- 区分输入空间、输出空间和辅助空间。
- 能分析变量、容器复制、哈希集合和递归调用栈的空间开销。
- 理解原地算法、复制型算法和时间空间权衡。
- 空间来源
- 输入数据
- 输出结果
- 辅助变量
- 临时容器
- 缓存
- 递归调用栈
- 常见复杂度
- O(1)
- O(log n)
- O(n)
- O(n²)
- 算法类型
- 原地算法
- 复制型算法
- 流式算法
- 递归算法
- 权衡
- 时间换空间
- 空间换时间
- 可读性
- 副作用
- 并发安全
问题背景或应用场景
在小规模输入下,多创建一个列表通常不会产生明显问题。但在生产环境中,输入规模可能达到百万级甚至更大。例如:
- 读取一百万条订单并复制三份列表。
- 对大型文件一次性读取全部内容。
- 为每个用户建立临时缓存。
- 对深度很大的树使用递归遍历。
- 在高并发接口中创建大量短生命周期对象。
这些操作可能导致:
- 内存占用快速增长。
- 垃圾回收频率上升。
- 响应时间抖动。
- 进程被系统终止。
- 容器触发内存限制。
- 递归深度超过语言限制。
因此,评价算法时不能只看运行时间,还要分析额外空间。
核心原理
1. 输入空间
输入空间用于保存调用方提供的数据。例如,函数接收一个长度为 n 的列表,该列表本身占用 O(n) 空间。
在很多算法分析中,默认输入已经存在,因此更关注算法额外申请的辅助空间。
2. 输出空间
如果算法需要返回一个长度为 n 的新列表,输出本身需要 O(n) 空间。
有些教材把输出空间单独讨论,有些会把它包含在总空间中。分析时应明确口径。
3. 辅助空间
辅助空间是算法运行期间额外使用的内存,包括:
- 固定数量变量。
- 临时列表。
- 集合和字典。
- 缓存表。
- 递归调用栈。
- 中间字符串。
- 切片副本。
4. O(1) 辅助空间
如果算法只使用固定数量变量,不随 n 增长,辅助空间为 O(1)。例如遍历列表求和:
def total(values: list[int]) -> int:
result = 0
for value in values:
result += value
return result无论列表多长,只使用 result 和 value 等固定变量。
5. O(n) 辅助空间
如果算法创建与输入规模同阶的新容器,辅助空间为 O(n)。例如复制列表:
def copy_values(values: list[int]) -> list[int]:
result = []
for value in values:
result.append(value)
return result6. 递归调用栈
递归函数每调用一次,运行时通常需要保存:
- 参数。
- 局部变量。
- 返回位置。
- 当前执行状态。
如果递归深度为 n,调用栈空间通常为 O(n)。如果每次把问题规模减半,递归深度通常为 O(log n)。
7. 原地算法
原地算法直接修改输入结构,只使用少量额外空间。例如原地反转列表,只需要左右两个索引和交换临时状态,因此辅助空间为 O(1)。原地算法的优点:
- 减少内存占用。
- 避免复制大规模数据。
原地算法的风险:
- 会修改调用方数据。
- 可能影响其他引用。
- 测试和调试时更容易出现副作用。
- 并发场景下需要更谨慎。
8. 时间与空间权衡
有些算法使用额外空间换取更快速度。例如判断重复值:
- 两层循环比较,不使用额外集合,时间 O(n²),空间 O(1)。
- 使用集合记录已见元素,时间通常 O(n),空间 O(n)。
工程中需要根据数据规模、内存限制和性能目标做权衡。
基础用法
示例一:固定变量
def find_max(values: list[int]) -> int:
max_value = values[0]
for value in values[1:]:
if value > max_value:
max_value = value
return max_value如果严格分析 Python 切片 values[1:],它会创建新列表,产生 O(n) 额外空间。为了保持 O(1) 辅助空间,可以改为索引遍历:
def find_max(values: list[int]) -> int:
max_value = values[0]
for index in range(1, len(values)):
if values[index] > max_value:
max_value = values[index]
return max_value这说明空间分析需要关注语言具体行为。
示例二:集合去重
def has_duplicate(values: list[int]) -> bool:
seen = set()
for value in values:
if value in seen:
return True
seen.add(value)
return False最坏情况下集合保存 n 个元素,因此空间复杂度为 O(n)。
示例三:矩阵
创建 n 行 n 列矩阵:
def create_matrix(size: int) -> list[list[int]]:
return [[0] * size for _ in range(size)]矩阵包含 n² 个元素,因此空间复杂度为 O(n²)。
完整可运行示例
from collections.abc import Sequence
def reverse_copy(values: Sequence[int]) -> list[int]:
result: list[int] = []
for index in range(len(values) - 1, -1, -1):
result.append(values[index])
return result
def reverse_in_place(values: list[int]) -> None:
left = 0
right = len(values) - 1
while left < right:
values[left], values[right] = values[right], values[left]
left += 1
right -= 1
def has_duplicate_with_nested_loop(values: Sequence[int]) -> bool:
for first in range(len(values)):
for second in range(first + 1, len(values)):
if values[first] == values[second]:
return True
return False
def has_duplicate_with_set(values: Sequence[int]) -> bool:
seen: set[int] = set()
for value in values:
if value in seen:
return True
seen.add(value)
return False
def main() -> None:
original = [10, 20, 30, 40, 50]
copied = reverse_copy(original)
changed = original.copy()
changed_id_before = id(changed)
reverse_in_place(changed)
changed_id_after = id(changed)
unique_values = [1, 2, 3, 4]
duplicate_values = [1, 2, 3, 2]
print(f"original: {original}")
print(f"copy result: {copied}")
print(f"in-place result: {changed}")
print(f"same list object: {changed_id_before == changed_id_after}")
print(
"nested loop duplicate:",
has_duplicate_with_nested_loop(duplicate_values),
)
print(
"set duplicate:",
has_duplicate_with_set(duplicate_values),
)
print(
"set unique:",
has_duplicate_with_set(unique_values),
)
if __name__ == "__main__":
main()运行命令:
python lesson_01_04.py预期输出
original: [10, 20, 30, 40, 50]
copy result: [50, 40, 30, 20, 10]
in-place result: [50, 40, 30, 20, 10]
same list object: True
nested loop duplicate: True
set duplicate: True
set unique: False示例复杂度分析
reverse_copy:
- 时间复杂度:O(n)。
- 辅助空间复杂度:O(n)。
- 不修改原列表。
reverse_in_place:
- 时间复杂度:O(n)。
- 辅助空间复杂度:O(1)。
- 会修改传入列表。
has_duplicate_with_nested_loop:
- 最坏时间复杂度:O(n²)。
- 辅助空间复杂度:O(1)。
has_duplicate_with_set:
- 平均时间复杂度:O(n)。
- 辅助空间复杂度:O(n)。
这组示例展示了典型的时间空间权衡。
Tips
- 空间复杂度关注增长数量级,不是精确字节数。
- 分析时明确是否包含输入空间和输出空间。
- 不要遗漏递归调用栈。
- Python 切片通常会创建新对象。
- 列表推导式会创建完整列表。
- 生成器可以按需产生元素,减少峰值内存。
- 原地算法会修改输入,应在接口文档中明确。
- 集合和字典通常用额外空间换取更快查找。
- 高并发场景下,单次请求的小额内存也可能被并发倍数放大。
- 大文件处理优先考虑分块和流式读取。
- 缓存可以提升速度,但必须考虑容量和淘汰策略。
- 递归算法需要同时考虑时间复杂度和最大深度。
常见错误
错误一:只统计显式创建的列表
递归调用栈、切片、字符串拼接和字典缓存也会占用空间。
错误二:认为没有 new 就没有额外空间
在 Python 中,切片、排序副本和某些表达式会隐式创建对象。
错误三:把输入空间全部算作辅助空间
如果题目只询问额外空间,应排除已存在的输入数据。
错误四:认为原地算法一定更好
原地算法可能破坏输入,增加副作用和并发风险。
错误五:忽略输出结果
返回一个长度为 n 的结果列表,本身就需要 O(n) 空间。
错误六:只关注平均内存
峰值内存更可能决定程序是否触发内存限制。
错误七:把对象标识当成空间证明
对象标识只能说明是否是同一个对象,不能精确代表内存大小。
本课练习
- 分析遍历求和的辅助空间。
- 分析返回所有偶数的新列表的空间复杂度。
- 分析使用集合去重的时间和空间复杂度。
- 实现原地交换列表首尾元素。
- 实现返回新列表的反转函数。
- 比较原地反转和复制反转的适用场景。
- 分析递归计算阶乘的调用栈空间。
- 创建 n × n 矩阵,并分析空间复杂度。
- 将一次性读取文件改为逐行处理。
- 思考在以下场景中更关注时间还是空间:
- 手机端处理大图片。
- 服务器缓存热点数据。
- 离线批量统计。
- 实时交易接口。