Python 设置切片复杂度
Python Set Slice Complexity
假设我有两个名为a和b的列表，大小都是n，我想做如下切片设置操作，k < n
a[:k] = b[:k]
在 Python wiki 的 Time Complexity 页面中，它表示切片设置的复杂度为 O(n+k)，其中 k 是切片的长度。我只是无法理解为什么在上述情况下它不只是 O(k)。
我知道切片 returns 一个新列表，所以它是 O(k)，而且我知道列表以连续的方式保存它的数据，所以在中间插入一个项目需要 O(k) (n) 时间。但是上面的操作很容易在 O(k) 时间内完成。我错过了什么吗？
此外，是否有文档可以让我找到有关此类问题的详细信息？我应该查看 CPython 实现吗？
谢谢。
你是对的，如果你想知道确切的细节，最好使用源代码。设置切片的CPython实现是in listobject.c.
如果我没看错的话，它会...
- 计算您要插入（或删除）多少个新元素！
- 将列表中的 n 个现有元素移动到足够多的位置以便为新元素腾出空间，在最坏的情况下（当列表中的每个元素都必须移动时）需要 O(n) 时间。
- 将新元素复制到刚刚创建的 space 中，花费 O(k) 时间。
加起来为 O(n+k)。
当然，您的情况可能不是最坏的情况：您正在更改列表的最后 k 个元素，因此可能根本不需要移动，从而将复杂度降低到您预期的 O(k) .然而，一般情况下并非如此。
O(n+k) 是平均情况，其中包括必须扩大或缩小列表以调整插入的元素数量以替换原始切片。
在您的情况下，您用相同数量的新元素替换切片，实现只需要 O(k) 步。但是考虑到插入和删除元素数量的所有可能组合，average 情况必须将列表中的 n 个剩余元素向上或向下移动。
请参阅 list_ass_slice function 以了解确切的实施方式。
假设我有两个名为a和b的列表，大小都是n，我想做如下切片设置操作，k < n
a[:k] = b[:k]
在 Python wiki 的 Time Complexity 页面中，它表示切片设置的复杂度为 O(n+k)，其中 k 是切片的长度。我只是无法理解为什么在上述情况下它不只是 O(k)。
我知道切片 returns 一个新列表，所以它是 O(k)，而且我知道列表以连续的方式保存它的数据，所以在中间插入一个项目需要 O(k) (n) 时间。但是上面的操作很容易在 O(k) 时间内完成。我错过了什么吗？
此外，是否有文档可以让我找到有关此类问题的详细信息？我应该查看 CPython 实现吗？
谢谢。
你是对的，如果你想知道确切的细节，最好使用源代码。设置切片的CPython实现是in listobject.c.
如果我没看错的话，它会...
- 计算您要插入（或删除）多少个新元素！
- 将列表中的 n 个现有元素移动到足够多的位置以便为新元素腾出空间，在最坏的情况下（当列表中的每个元素都必须移动时）需要 O(n) 时间。
- 将新元素复制到刚刚创建的 space 中，花费 O(k) 时间。
加起来为 O(n+k)。
当然，您的情况可能不是最坏的情况：您正在更改列表的最后 k 个元素，因此可能根本不需要移动，从而将复杂度降低到您预期的 O(k) .然而，一般情况下并非如此。
O(n+k) 是平均情况，其中包括必须扩大或缩小列表以调整插入的元素数量以替换原始切片。
在您的情况下，您用相同数量的新元素替换切片，实现只需要 O(k) 步。但是考虑到插入和删除元素数量的所有可能组合，average 情况必须将列表中的 n 个剩余元素向上或向下移动。
请参阅 list_ass_slice function 以了解确切的实施方式。