数据结构与算法 / 系统课时
时间复杂度与空间复杂度
时间复杂度与空间复杂度
分析算法时,不能只看程序能否得到正确结果,还要判断输入规模增大后需要多少计算与内存。本课将用同一组求和算法对比时间复杂度、输入空间与辅助空间,并建立可复用的分析步骤。
学习目标
- 区分时间复杂度、总空间复杂度与辅助空间复杂度。
- 根据循环、递归和临时数据结构判断复杂度。
- 说明输入空间、输出空间是否计入分析结果。
核心原理
时间复杂度描述基本操作次数随输入规模 的增长趋势,而不是某台机器上的实际运行秒数。空间复杂度描述算法执行期间占用的存储量,通常需要进一步区分输入空间和辅助空间。
- 输入空间:保存调用者传入数据所需的空间。例如长度为 的数组占用 空间。
- 辅助空间:算法为了完成计算额外申请的空间,包括临时数组、集合、对象和递归调用栈。
- 输出空间:保存返回结果所需的空间。是否计入辅助空间必须在分析时明确说明。
本课比较辅助空间时排除调用者已有输入和返回结果,统计同时存活的额外内存峰值。总空间要检查输入、辅助状态和输出是否同时存活、是否共享。若生命周期不同,直接把各自峰值相加只能得到上界。
| 实现方式 | 时间复杂度 | 辅助空间复杂度 | 关键原因 |
|---|---|---|---|
| 单次循环求和 | 遍历 个元素,只保存常数个变量 | ||
| 递归求和 | 每个元素处理一次,递归助手最深有 层 | ||
| 复制后求和 | 复制数组需要额外保存 个元素 |
分析时先确定输入规模,再统计主导操作。连续执行的代码取最大增长项;只有内层每轮开销相同才可直接用轮数相乘。一般对各轮成本求和,递归则分别计算调用次数与最大同时存活的帧数。
完整可运行示例
下面的 Python 3 程序使用三种方式计算同一数组的元素总和。三种实现的结果相同,但辅助空间不同。
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. 把实际运行时间当成时间复杂度
同一算法在不同硬件、语言和数据上耗时不同。复杂度关心的是增长趋势,因此应统计操作次数与 的关系,而不是只比较一次计时结果。
2. 忽略递归调用栈
递归函数即使没有创建数组,也可能占用线性空间。递归深度为 时,调用栈通常需要 辅助空间;Python 有递归深度限制,这个递归版只用于小规模演示。若写成逐层传 values[1:],每层都会创建新的切片,复制总量可达平方级。帧同时保留各自的切片时,存活空间也可到平方级。
3. 混淆输入空间与辅助空间
长度为 的输入数组本身占用 ,但循环求和没有再申请同规模存储,所以辅助空间仍是 。报告结论时应明确采用哪一种口径。
本课练习
- 分析一个包含两个连续单层循环的函数,分别写出时间复杂度和辅助空间复杂度,并说明为什么两个 循环合并后仍为 。
- 编写一个查找数组最大值的循环版本,要求辅助空间为 ,并用长度为 0 和长度为 1 的输入验证边界处理。
- 分析归并排序的时间复杂度、递归栈空间和临时数组空间,分别给出主导项及其来源。
本课总结
- 时间复杂度衡量操作次数的增长趋势,空间复杂度必须说明统计的是总空间还是辅助空间。
- 循环、递归和临时数据结构都可能影响复杂度,递归调用栈不能忽略。
- 输出结论前应先确定输入规模与统计口径,再保留增长最快的主导项。
下一课预告
下一课将学习「大 O 记号」,用形式化不等式表达渐进上界,并判断不同函数之间的增长关系。