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

时间复杂度与空间复杂度

时间复杂度与空间复杂度

分析算法时,不能只看程序能否得到正确结果,还要判断输入规模增大后需要多少计算与内存。本课将用同一组求和算法对比时间复杂度、输入空间与辅助空间,并建立可复用的分析步骤。

学习目标

  • 区分时间复杂度、总空间复杂度与辅助空间复杂度。
  • 根据循环、递归和临时数据结构判断复杂度。
  • 说明输入空间、输出空间是否计入分析结果。

核心原理

时间复杂度描述基本操作次数随输入规模 nn 的增长趋势,而不是某台机器上的实际运行秒数。空间复杂度描述算法执行期间占用的存储量,通常需要进一步区分输入空间和辅助空间。

  • 输入空间:保存调用者传入数据所需的空间。例如长度为 nn 的数组占用 O(n)O(n) 空间。
  • 辅助空间:算法为了完成计算额外申请的空间,包括临时数组、集合、对象和递归调用栈。
  • 输出空间:保存返回结果所需的空间。是否计入辅助空间必须在分析时明确说明。

本课比较辅助空间时排除调用者已有输入和返回结果,统计同时存活的额外内存峰值。总空间要检查输入、辅助状态和输出是否同时存活、是否共享。若生命周期不同,直接把各自峰值相加只能得到上界。

实现方式 时间复杂度 辅助空间复杂度 关键原因
单次循环求和 O(n)O(n) O(1)O(1) 遍历 nn 个元素,只保存常数个变量
递归求和 O(n)O(n) O(n)O(n) 每个元素处理一次,递归助手最深有 n+1n+1 层
复制后求和 O(n)O(n) O(n)O(n) 复制数组需要额外保存 nn 个元素

分析时先确定输入规模,再统计主导操作。连续执行的代码取最大增长项;只有内层每轮开销相同才可直接用轮数相乘。一般对各轮成本求和,递归则分别计算调用次数与最大同时存活的帧数。

完整可运行示例

下面的 Python 3 程序使用三种方式计算同一数组的元素总和。三种实现的结果相同,但辅助空间不同。

python
def sum_iterative(values: list[int]) -> int:
    total = 0
    for value in values:
        total += value
    return total

def sum_recursive(values: list[int]) -> int:
    def visit(index):
        if index == len(values):
            return 0
        return values[index] + visit(index + 1)

    return visit(0)

def sum_with_copy(values: list[int]) -> int:
    work = values.copy()
    total = 0
    while work:
        total += work.pop()
    return total

numbers = [2, 4, 6, 8]
print("循环求和:", sum_iterative(numbers))
print("递归求和:", sum_recursive(numbers))
print("复制后求和:", sum_with_copy(numbers))
print("原始输入:", numbers)

保存为 complexity_demo.py 后运行,三种输出都为 20,原始列表仍为 [2, 4, 6, 8]。按列表元素为常数大小的引用、每次整数加法为常数成本的模型,三种实现时间均为 Θ(n)。迭代只用常数个状态。递归助手包含终止帧,最多 n+1 层。复制版另保存 n 个引用,仍共享原来的元素对象。这里的常数空间指固定数量的机器字或状态变量,在 Python 大整数的字节成本模型下还要算累加结果的位长。

常见错误

1. 把实际运行时间当成时间复杂度

同一算法在不同硬件、语言和数据上耗时不同。复杂度关心的是增长趋势,因此应统计操作次数与 nn 的关系,而不是只比较一次计时结果。

2. 忽略递归调用栈

递归函数即使没有创建数组,也可能占用线性空间。递归深度为 nn 时,调用栈通常需要 O(n)O(n) 辅助空间;Python 有递归深度限制,这个递归版只用于小规模演示。若写成逐层传 values[1:],每层都会创建新的切片,复制总量可达平方级。帧同时保留各自的切片时,存活空间也可到平方级。

3. 混淆输入空间与辅助空间

长度为 nn 的输入数组本身占用 O(n)O(n),但循环求和没有再申请同规模存储,所以辅助空间仍是 O(1)O(1)。报告结论时应明确采用哪一种口径。

本课练习

  1. 分析一个包含两个连续单层循环的函数,分别写出时间复杂度和辅助空间复杂度,并说明为什么两个 O(n)O(n) 循环合并后仍为 O(n)O(n)。
  2. 编写一个查找数组最大值的循环版本,要求辅助空间为 O(1)O(1),并用长度为 0 和长度为 1 的输入验证边界处理。
  3. 分析归并排序的时间复杂度、递归栈空间和临时数组空间,分别给出主导项及其来源。

本课总结

  • 时间复杂度衡量操作次数的增长趋势,空间复杂度必须说明统计的是总空间还是辅助空间。
  • 循环、递归和临时数据结构都可能影响复杂度,递归调用栈不能忽略。
  • 输出结论前应先确定输入规模与统计口径,再保留增长最快的主导项。

下一课预告

下一课将学习「大 O 记号」,用形式化不等式表达渐进上界,并判断不同函数之间的增长关系。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

时间复杂度与空间复杂度

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

登录哪都通