时间戳

首页 > 解决方案 > 替换列表中的元素是否等同于删除然后插入元素？或者只是访问它们？

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

问题描述

我想弄清楚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)？或者是其他东西？谢谢！

标签： pythonlisttime-complexity

解决方案

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

# 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 实现效率较低，我会感到非常惊讶。

推荐阅读