基于Big-O表示法计算给定Python代码的算法复杂度

核心结论 #

这段代码的实际时间复杂度是 O(n²)。很多人初次分析时会误判为O(n)，根本原因是忽略了Python列表切片操作的拷贝开销，没有把这部分成本计入复杂度计算。 #

复杂度拆解 #

• 递归调用次数：每轮递归会将待处理的列表长度减少1，直到列表长度为1时触发终止条件。对长度为n的输入列表，总共会产生n-1次递归调用，单看这部分的逻辑规模是O(n)级别的。
• 切片操作的核心开销：代码中numList[1:]不是无成本的引用切片，Python在执行列表切片时，会生成一个全新的列表对象，把原列表从索引1开始的所有元素逐一拷贝到新列表中。每次切片的拷贝耗时和切片后的列表长度成正比：
  • 第一次调用：拷贝n-1个元素
  • 第二次调用：拷贝n-2个元素
  • ……
  • 倒数第二次调用：拷贝1个元素
    把所有拷贝操作的元素总数累加，总拷贝量为 (n-1)+(n-2)+…+1 = n(n-1)/2，这部分操作的增长规模和n²正相关，是整体时间复杂度被拉高的核心原因。
• 空间复杂度：因为递归需要等待内层调用返回后才能执行加法运算，调用栈的最大深度为n层；加上每一层切片生成的临时列表会在栈帧留存直到对应递归层执行完毕，所有临时列表的总长度累加后同样是和n²正相关，因此整体空间复杂度也是 O(n²)。如果把切片逻辑替换为「传入原列表+起止索引」的实现方式，消除冗余的列表拷贝，时间和空间复杂度都会回落到纯O(n)的水平。

待分析的代码 #

def listsum(numList):
   if len(numList) == 1:
        return numList[0]
   else:
        return numList[0] + listsum(numList[1:])

分析提醒：很多同类递归算法的复杂度分析，容易只关注递归的层数，忽略每一轮递归内部执行的操作本身的成本——如果每轮递归的操作不是固定时间的常数级，就需要把这部分操作的规模和递归层数结合起来计算总复杂度。

内容的提问来源于stack exchange，提问作者Chammur