列表切片的Big-O [英] Big-O of list slicing
问题描述
说我有一些Python列表,my_list
,其中包含N个元素.可以使用my_list[i_1]
为单个元素建立索引,其中i_1
是所需元素的索引.但是,Python列表也可能被索引为my_list[i_1:i_2]
,其中需要从i_1
到i_2
的列表切片".切成大小为N的列表的Big-O(最坏情况)表示法是什么?
Say I have some Python list, my_list
which contains N elements. Single elements may be indexed by using my_list[i_1]
, where i_1
is the index of the desired element. However, Python lists may also be indexed my_list[i_1:i_2]
where a "slice" of the list from i_1
to i_2
is desired. What is the Big-O (worst-case) notation to slice a list of size N?
就我个人而言,如果我正在编码切片器",我会从i_1
迭代到i_2
,生成一个新列表并返回它,暗示O(N),这是Python的方式吗?
Personally, if I were coding the "slicer" I would iterate from i_1
to i_2
, generate a new list and return it, implying O(N), is this how Python does it?
谢谢
推荐答案
获取切片是O(i_2 - i_1
).这是因为Python的列表内部表示是一个数组,因此您可以从i_1
开始并迭代到i_2
.
Getting a slice is O(i_2 - i_1
). This is because Python's internal representation of a list is an array, so you can start at i_1
and iterate to i_2
.
有关更多信息,请参见Python 时间复杂度Wiki条目
For more information, see the Python time complexity wiki entry
您还可以在 CPython源代码<中查看实现/a>如果愿意.
You can also look at the implementation in the CPython source if you want to.
这篇关于列表切片的Big-O的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!