假设我有两个名为a和b的列表，两个列表的大小均为n，并且我想用k
a[:k] = b[:k]
在Python Wiki的Time Complexity页面中，它说切片设置的复杂度为O(n + k)，其中k是切片的长度。我只是不明白为什么在上述情况下它不仅是O(k)。
我知道切片会返回一个新列表，所以它是O(k)，并且我知道列表以连续的方式保存其数据，因此在中间插入一个项目将花费O(n)的时间。但是上述操作可以很容易地在O(k)时间内完成。我想念什么吗？
此外，是否有文档可以找到有关此类问题的详细信息？我应该研究CPython的实现吗？
谢谢。
最佳答案
O(n + k)是平均情况，包括必须增加或缩小列表才能调整插入的元素数量以替换原始切片。
在您的情况下，用相等数量的新元素替换切片，实现仅需O(k)个步骤。但是，考虑到插入和删除的元素数量的所有可能组合，平均情况下必须向上或向下移动列表中的n个剩余元素。
有关确切的实现，请参见 list_ass_slice function。
关于Python Set Slice的复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/34356780/