Python 集合切片复杂性

Question

假设我有两个列表，分别为a和b，大小都是n，我想对k < n做如下切片设置操作

a[:k] = b[:k]

在 Python wiki 的 Time Complexity 中它说切片设置的复杂度是 O(n+k)，其中 k 是切片的长度。我只是不明白为什么在上述情况下它不只是 O(k)。

我知道切片会返回一个新列表，所以它是 O(k)，而且我知道该列表以连续的方式保存其数据，因此在中间插入一个项目将花费 O(n) 时间。但是上面的操作很容易在 O(k) 时间内完成。我错过了什么吗？

此外，是否有文档可以让我找到有关此类问题的详细信息？我应该研究 CPython 实现吗？

谢谢。

Answer 1

O(n+k) 是平均情况，其中包括必须扩大或缩小列表以调整插入的元素数量以替换原始切片。

在您的情况下，您用相同数量的新元素替换切片，实现只需要 O(k) 个步骤。但是考虑到插入和删除的元素数量的所有可能组合，平均 情况必须将列表中的 n 个剩余元素向上或向下移动。

参见 list_ass_slice function用于确切的实现。