Python中sum(a, [])扁平化二维数组的原理及时间复杂度解析

一、分步执行逻辑 #

Python内置的sum()函数原型是sum(iterable, start)，其中：

• iterable是要累加的可迭代对象（这里就是二维数组的子数组集合）
• start是累加的初始值，默认是0，这里我们传了空列表[]

拿你的示例代码来说：

a = [[4,2,5],[1,8,2],[7,5,6]]
flat = sum(a, [])

具体执行步骤如下：

1. 初始累加值为start传入的空列表[]
2. 取第一个子数组[4,2,5]，和当前累加值做列表拼接：[] + [4,2,5] = [4,2,5]，更新累加值
3. 取第二个子数组[1,8,2]，和当前累加值拼接：[4,2,5] + [1,8,2] = [4,2,5,1,8,2]，再次更新累加值
4. 取第三个子数组[7,5,6]，和当前累加值拼接：[4,2,5,1,8,2] + [7,5,6] = [4,2,5,1,8,2,7,5,6]，得到最终一维数组

本质就是把二维数组里的每个子数组，依次拼接到初始空列表上，最终实现二维转一维。

二、时间复杂度问题：确实是平方级 #

当数组规模较大时，sum(array_2d, [])的时间复杂度为O(n²)，核心原因在于Python列表的拼接特性：

列表通过+拼接时，会创建一个全新的列表，并且需要把两个列表中的所有元素都复制到新列表里。

假设二维数组有m个子数组，每个子数组平均长度为k，总元素数N = m*k：

• 第一次拼接：复制k个元素（空列表+第一个子数组）
• 第二次拼接：复制2k个元素（前一次结果+第二个子数组）
• 第三次拼接：复制3k个元素
• ...
• 第m次拼接：复制mk个元素

总复制操作次数为k*(1+2+...+m) = k*m(m+1)/2，当m很大时，这个值与m²成正比，属于平方级时间复杂度。如果每个子数组长度为1（k=1），总元素数N=m，总复制次数就是N(N+1)/2，完全是O(N²)量级。

对比更高效的方法（比如列表推导式[x for sub in array_2d for x in sub]或itertools.chain.from_iterable(array_2d)），这些方法仅需遍历所有元素一次，复制N次，时间复杂度为O(N)，大数据量下性能差距会非常明显。

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