python - 枚举的复杂度

Question

我看到很多关于 python 内置方法的运行时复杂性的问题，并且很多方法都有很多答案(例如 https://wiki.python.org/moin/TimeComplexity 、 https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt 、 Cost of len() function 等。 )

我没有看到任何地址枚举。我知道它至少返回一个新数组(索引)，但生成该数组需要多长时间，另一个数组是否只是原始数组？

换句话说，我假设创建新数组(迭代)的时间复杂度为 O(n)，原始数组的重用时间为 O(1)...总共为 O(n)(我认为)。副本的另一个 O(n) 是 O(n^2)，还是其他什么...？

Answer 1

枚举函数返回一个迭代器。描述了迭代器的概念 here .

基本上这意味着迭代器初始化为指向列表的第一项，然后在每次调用其 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