Python中不同长度列表切片赋值操作的时间复杂度是多少

我们讨论的是a[i:i+len1] = b[j:j+len2]这一操作的时间复杂度，基于CPython的标准实现逻辑，结论分两种场景：

核心开销构成 #

整个操作的开销由两部分组成：

• 读取源切片b的所有元素：固定需要*O(len2)*的时间，要把len2个元素从b中复制出来
• 处理目标列表a的开销，这部分由目标切片长度和源切片长度是否匹配决定

注：如果列表扩容涉及底层数组的重新分配，会带来额外开销，但均摊后不会改变下述大O时间复杂度量级。

场景1：len1 = len2（源切片和目标切片长度相等） #

这种场景下不需要移动a中目标区间之外的元素，只需要把读出来的len2个元素逐个覆盖到a的i:i+len1区间即可，处理a的开销为O(len1) = O(len2)。
总时间复杂度为 O(len2)。 #

场景2：len1 ≠ len2（源切片和目标切片长度不等） #

这种场景下列表a的总长度会发生变化，需要移动a中目标区间之后的所有元素来适配长度变化：

• 如果len2 > len1：目标区间之后的元素整体向后偏移len2 - len1位
• 如果len2 < len1：目标区间之后的元素整体向前偏移len1 - len2位
  这部分移动元素的开销为O(len(a) - i - len1)，加上读取源切片和覆盖目标区间的开销，总时间复杂度为 O(len2 + (len(a) - i))。

常见特例验证 #

• 如果是在列表末尾追加切片，也就是i = len(a)，目标区间之后没有元素，不管len1和len2是否相等，移动开销都是0，总时间复杂度为O(len2)，和列表extend()方法的时间复杂度一致
• 如果是替换整个列表，也就是a[:] = b[:]，目标区间之后没有元素，总时间复杂度为O(len(b))

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