列表切片的大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 时间复杂度wiki条目

如果需要,您还可以查看CPython源代码中的实现.

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。