python - 列表切片的大 O

Question

假设我有一些 Python 列表，my_list，其中包含 N 个元素。单个元素可以使用 my_list[i_1] 进行索引，其中 i_1 是所需元素的索引。但是，Python 列表也可以被索引为 my_list[i_1:i_2]，其中需要从 i_1 到 i_2 的列表“切片”。对大小为 N 的列表进行切片的 Big-O(最坏情况)表示法是什么？

就个人而言，如果我正在编写“切片器”，我会从 i_1 迭代到 i_2，生成一个新列表并返回它，这意味着 O(N) 是Python 是这样做的？

谢谢，

Answer 1

得到一个切片是 O(i_2 - i_1)。这是因为 Python 对列表的内部表示是一个数组，所以可以从 i_1 开始，迭代到 i_2。

有关详细信息，请参阅 Python Time Complexity wiki entry

您还可以查看 CPython source 中的实现如果你愿意的话。