python - 列表切片的大 O

Question

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

就个人而言，如果我正在编写“切片器”，我会从i_1to迭代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。