替换列表中的元素是否等同于删除然后插入元素？或者只是访问它们？

Question

我想弄清楚 replacing items in a list 是否是 equivalent 到 removing the items then inserting？ - 在这种情况下，它将是 O(n) 时间，而我知道访问列表中的元素是常数时间，所以替换元素是 O(1) 吗？

For example, nums = [1,2,3,4,5,6] 

temp = [8,8,8]

nums[2:5] = temp 

print(nums) 

-> [1,2,8,8,8,6]

这是 O(1) 操作还是 O(n) 操作？或者是其他东西？谢谢！

Answer 1

如 Python 文档中所述 here:

Time Complexity

O(k) for slice retrieval
O(n) for deletion
O(n+k) for slice assignment

所以这意味着切片分配（您所问的）是 O(n+k)。

Answer 2

时间复杂度为 O(1)（或 O(k)，其中 k 是切片的长度）

a = list(range(100))
b = list(range(100000))

timeit.timeit('a[50] = 10', globals=globals(),number=10000)
0.00039079999999103165
timeit.timeit('b[50] = 10', globals=globals(),number=10000)
0.00039970000000266737
timeit.timeit('b[5000] = 10', globals=globals(),number=10000)
0.0003963999999996304
timeit.timeit('b[5000:5005] = [10,11,12,13,14]', globals=globals(),number=10000)
0.0016413999999826956
 timeit.timeit('a[50:55] = [10,11,12,13,14]', globals=globals(),number=10000)
0.0016435999999657724

Answer 3

在CPython（大多数人使用的“官方”参考实现）中，algorithm大致如下（省略无关细节）：

# a[ilow:ihigh] = v

norig = ihigh - ilow
n = len(v)
d = n - norig
if d < 0:
    move a[ihigh:] to a[ihigh + d:]
    resize a to len(a) + d
elif d > 0:
    resize a to len(a) + d
    move a[ihigh:] to a[ihigh + d:]

这意味着，如果您将一个切片替换为另一个长度相等的切片，则实际上不会移动原始列表中的任何项目。所以操作是 O(k) 其中 k 是替换切片的长度，不管总长度 n 原始列表。

另一方面，如果您手动删除一个切片然后插入另一个切片，则实际上需要移动被删除切片之后的项目，因此您得到 O(n + k) 时间复杂度代替。

请注意，这是一个 CPython 实现细节，但如果其他 Python 实现效率较低，我会感到非常惊讶。

替换列表中的元素是否等同于删除然后插入元素？或者只是访问它们？

Is replacing elements in a list equivalent to removing then inserting elements? Or simply accessing them?

python

list

time-complexity

Time Complexity