枚举的复杂性

Question

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

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

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

Answer 1

假设采用朴素的方法（枚举复制数组，然后遍历它），您有 O(n) 的时间来复制数组，然后有 O(n) 的时间来遍历它。如果那只是 n 而不是 O(n)，你将有 2 * n 总时间，但这不是 O(n) 的工作方式;您所知道的是，它所花费的时间将是 n 的 some 倍数。这（基本上）就是 O(n) 的意思，所以在任何情况下，枚举函数都是 O(n) 时间总计。

Answer 2

正如 martineau 指出的那样，enumerate() 不会复制数组。相反，它 returns 一个用于遍历数组的对象。对 enumerate() 本身的调用是 O(1).

Answer 3

枚举函数returns 一个迭代器。迭代器的概念描述为 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

枚举的复杂性

Complexity of enumerate

python

arrays

big-o

enumerate

time-complexity