列表切片的时间复杂度（Big-O）

Question

假设我有一个 Python 列表 my_list，其中包含 N 个元素。要获取单个元素，可以使用 my_list[i_1] 获取索引为 i_1 的元素。此外，Python 列表还支持对列表进行切片操作，如 my_list[i_1:i_2]，表示获取从索引 i_1 到 i_2 的子列表。对于大小为 N 的列表进行切片操作的最坏时间复杂度是什么？

就我个人而言，如果我编写“切片器”，我会从 i_1 迭代到 i_2，生成一个新列表并返回它，这意味着时间复杂度为 O(N)，Python 是这样实现的吗？

谢谢。

- mjgpy3

Answer 1

获取切片的时间复杂度为 O(i_2 - i_1)。这是因为Python内部使用数组来表示列表，所以您可以从i_1开始迭代到i_2。

有关更多信息，请参阅Python时间复杂度维基条目。

如果您想了解更多，请查看CPython源代码实现。

- Sam Mussmann

---

我只需要my_list[1:]，但需要频繁执行，因此它的复杂度似乎会比my_list高一倍。我的列表大小固定，元素可能会更改值。保留对固定列表切片的引用有多昂贵？ - uuu777

更新：我编写了一个自定义的可迭代类，它可以遍历我的现有列表，不应该有任何惩罚。 - uuu777

Answer 2

根据 http://wiki.python.org/moin/TimeComplexity，时间复杂度为O(k)，其中k是切片大小。

- Joran Beasley

Answer 3

对于一个大小为N的列表和一个大小为M的切片，迭代实际上只有O（M），而不是O（N）。由于M通常<< N，因此这会产生很大的差异。

事实上，如果您考虑一下您的解释，您就可以看到为什么了。您只是从i_1到i_2迭代，而不是从0到i_1，然后从i_1到i_2。

- abarnert