列表切片的Big-O

Question

假设我有一些Python列表，my_list，其中包含N个元素。可以使用my_list[i_1]索引单个元素，其中i_1是所需元素的索引。然而，Python列表也可以被索引为my_list[i_1:i_2]，其中需要从i_1到i_2的列表的“片段”。什么是Big-O（最坏情况）符号来分割大小为N的列表？

就我个人而言，如果我正在编写“切片器”，我将从i_1迭代到i_2，生成一个新列表并返回它，这意味着O（N），这是Python的工作方式吗？

谢谢你

Answer 1

获取切片是O（i_2 - i_1）。这是因为Python对列表的内部表示是一个数组，因此您可以从i_1开始并迭代到i_2。

有关更多信息，请参见Pythontime 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。