数据结构与算法 / 系统课时

空间复杂度的基本概念

空间复杂度的基本概念

学习目标

  • 理解空间复杂度描述额外内存随输入规模增长的趋势。
  • 区分输入空间、输出空间和辅助空间。
  • 能分析变量、容器复制、哈希集合和递归调用栈的空间开销。
  • 理解原地算法、复制型算法和时间空间权衡。
  • 空间来源
    • 输入数据
    • 输出结果
    • 辅助变量
    • 临时容器
    • 缓存
    • 递归调用栈
  • 常见复杂度
    • O(1)
    • O(log n)
    • O(n)
    • O(n²)
  • 算法类型
    • 原地算法
    • 复制型算法
    • 流式算法
    • 递归算法
  • 权衡
    • 时间换空间
    • 空间换时间
    • 可读性
    • 副作用
    • 并发安全

问题背景或应用场景

在小规模输入下,多创建一个列表通常不会产生明显问题。但在生产环境中,输入规模可能达到百万级甚至更大。例如:

  • 读取一百万条订单并复制三份列表。
  • 对大型文件一次性读取全部内容。
  • 为每个用户建立临时缓存。
  • 对深度很大的树使用递归遍历。
  • 在高并发接口中创建大量短生命周期对象。

这些操作可能导致:

  • 内存占用快速增长。
  • 垃圾回收频率上升。
  • 响应时间抖动。
  • 进程被系统终止。
  • 容器触发内存限制。
  • 递归深度超过语言限制。

因此,评价算法时不能只看运行时间,还要分析额外空间。

核心原理

1. 输入空间

输入空间用于保存调用方提供的数据。例如,函数接收一个长度为 n 的列表,该列表本身占用 O(n) 空间。

在很多算法分析中,默认输入已经存在,因此更关注算法额外申请的辅助空间。

2. 输出空间

如果算法需要返回一个长度为 n 的新列表,输出本身需要 O(n) 空间。

有些教材把输出空间单独讨论,有些会把它包含在总空间中。分析时应明确口径。

3. 辅助空间

辅助空间是算法运行期间额外使用的内存,包括:

  • 固定数量变量。
  • 临时列表。
  • 集合和字典。
  • 缓存表。
  • 递归调用栈。
  • 中间字符串。
  • 切片副本。

4. O(1) 辅助空间

如果算法只使用固定数量变量,不随 n 增长,辅助空间为 O(1)。例如遍历列表求和:

python
def total(values: list[int]) -> int:
    result = 0

    for value in values:
        result += value

    return result

无论列表多长,只使用 result 和 value 等固定变量。

5. O(n) 辅助空间

如果算法创建与输入规模同阶的新容器,辅助空间为 O(n)。例如复制列表:

python
def copy_values(values: list[int]) -> list[int]:
    result = []

    for value in values:
        result.append(value)

    return result

6. 递归调用栈

递归函数每调用一次,运行时通常需要保存:

  • 参数。
  • 局部变量。
  • 返回位置。
  • 当前执行状态。

如果递归深度为 n,调用栈空间通常为 O(n)。如果每次把问题规模减半,递归深度通常为 O(log n)。

7. 原地算法

原地算法直接修改输入结构,只使用少量额外空间。例如原地反转列表,只需要左右两个索引和交换临时状态,因此辅助空间为 O(1)。原地算法的优点:

  • 减少内存占用。
  • 避免复制大规模数据。

原地算法的风险:

  • 会修改调用方数据。
  • 可能影响其他引用。
  • 测试和调试时更容易出现副作用。
  • 并发场景下需要更谨慎。

8. 时间与空间权衡

有些算法使用额外空间换取更快速度。例如判断重复值:

  • 两层循环比较,不使用额外集合,时间 O(n²),空间 O(1)。
  • 使用集合记录已见元素,时间通常 O(n),空间 O(n)。

工程中需要根据数据规模、内存限制和性能目标做权衡。

基础用法

示例一:固定变量

python
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) 辅助空间,可以改为索引遍历:

python
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

这说明空间分析需要关注语言具体行为。

示例二:集合去重

python
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 列矩阵:

python
def create_matrix(size: int) -> list[list[int]]:
    return [[0] * size for _ in range(size)]

矩阵包含 n² 个元素,因此空间复杂度为 O(n²)。

完整可运行示例

python
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()

运行命令:

bash
python lesson_01_04.py

预期输出

text
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) 空间。

错误六:只关注平均内存

峰值内存更可能决定程序是否触发内存限制。

错误七:把对象标识当成空间证明

对象标识只能说明是否是同一个对象,不能精确代表内存大小。

本课练习

  1. 分析遍历求和的辅助空间。
  2. 分析返回所有偶数的新列表的空间复杂度。
  3. 分析使用集合去重的时间和空间复杂度。
  4. 实现原地交换列表首尾元素。
  5. 实现返回新列表的反转函数。
  6. 比较原地反转和复制反转的适用场景。
  7. 分析递归计算阶乘的调用栈空间。
  8. 创建 n × n 矩阵,并分析空间复杂度。
  9. 将一次性读取文件改为逐行处理。
  10. 思考在以下场景中更关注时间还是空间:
    • 手机端处理大图片。
    • 服务器缓存热点数据。
    • 离线批量统计。
    • 实时交易接口。
按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

空间复杂度的基本概念

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通