枚举的复杂性

Question

我看到很多关于建的方法Python的的运行时间复杂度的问题,有很多答案了很多的方法(例如https://wiki.python.org/moin/TimeComplexity,HTTPS:/ /www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt,LEN()的开销功能,等)

我没有看到任何枚举的内容.我知道它至少返回一个新数组(索引),但生成它需要多长时间,而另一个数组只是原始数组？

换句话说,我假设它是O(n)用于创建新数组(迭代)和O(1)用于重用原始数组...总共O(n)(我认为).副本的另一个O(n)是否为O(n ^ 2),或其他什么......？

Answer 1

enumerate-function返回一个迭代器.这里描述了迭代器的概念.

基本上这意味着迭代器初始化指向列表的第一项,然后每次调用next()方法时返回列表的下一个元素.

所以复杂性应该是:

初始化:O(1)

返回下一个元素:O(1)

返回所有元素:n*O(1)

请注意,枚举不会创建新的数据结构(元组列表或类似的东西)!它只是迭代现有列表,记住元素索引.

你可以自己尝试一下:

# First, create a list containing a lot of entries:
# (O(n) - executing this line should take some noticeable time)
a = [str(i) for i in range(10000000)] # a = ["0", "1", ..., "9999999"]

# Then call the enumeration function for a.
# (O(1) - executes very fast because that's just the initialization of the iterator.)
b = enumeration(a)

# use the iterator
# (O(n) - retrieving the next element is O(1) and there are n elements in the list.)
for i in b:
    pass  # do nothing

Answer 2

假设天真的方法(枚举重复数组,然后迭代它),你有O(n)时间来复制数组,然后O(n)时间迭代它.如果那只是n而不是O(n),你将有2*n的总时间,但这不是O(n)的工作方式; 你所知道的是,它所花费的时间将是n的一些倍数.这是(基本上)O(n)的意思,无论如何,枚举函数是O(n)时间总和.

Answer 3

正如 martineau 指出的那样，enumerate()不会复制数组。相反，它返回一个用于迭代数组的对象。对自身的调用enumerate()是 O(1)。