python - 将切片分配给不同长度的另一个列表切片的Python时间复杂度

Question

假设我有两个名为aand的列表b，并且我想将b[j:j+len2]带有 len2 元素的切片分配给a[i:i+len1]带有 len1 元素的切片，那么这个操作的时间复杂度是多少？

a[i:i+len1] = b[j:j+len2]

标签： pythontime-complexityslice

Answer 1

如果len1 == len2那么那是O(len1)因为它相当于循环：

for n in range(len1):
    a[i+n] = b[j+n]

但是如果长度不同，则a必须移动切片后的元素以打开或关闭b切片所需的空间。如果列表在增长，则可能需要重新定位整个列表以腾出空间。这使得最坏情况变得复杂O(len(a) + len2)。