Python列表插入时间复杂度问询：A[0:0]=B的复杂度是O(N²)吗？

结论：不是O(N²)，而是O(N)。

原因如下：

• 首先要区分「逐个插入元素」和「切片赋值」的本质差异：
  • 如果是通过循环执行for item in B: A.insert(0, item)，这种情况确实是O(N²)——因为每次insert(0)都需要将A中现有所有元素后移一位，第一次移动N个元素，第二次移动N+1个，直到最后一次移动2N-1个，总操作次数属于O(N²)级别。
  • 而A[0:0] = B是Python列表的批量切片赋值操作，底层做了针对性优化：它会直接计算所需的总空间，先把B的所有元素一次性复制到A的起始位置，再将原A的所有元素整体向后平移N个位置（B的长度为N）。整个过程只涉及两次线性操作：复制B的N个元素、移动原A的N个元素，总操作次数是O(N + N) = O(N)。

简单来说，切片赋值是底层一次性完成的批量操作，并非多次单个插入的叠加，因此时间复杂度是线性级，而非平方级。

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