列表切片的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的列表的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中查看实现。

Answer 2

根据http://wiki.python.org/moin/TimeComplexity

它是O（k），其中k是切片大小

Answer 3

对于大小为N的列表和大小为M的切片，实际上迭代仅是O（M），而不是O（N）。由于M通常是<< N，所以差异很大。

实际上，如果您考虑一下您的解释，您会明白为什么。您只从i_1迭代到i_2，而不是从0迭代到i_1，然后再从I_1迭代到i_2。