枚举的复杂性

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

正如martineau所指出的，enumerate()并不复制数组。相反，它返回一个用于在数组上迭代的对象。对enumerate()本身的调用是O（1）。在

Answer 2

枚举函数返回迭代器。迭代器的概念描述为here。在

基本上，这意味着迭代器初始化时指向列表的第一项，然后在每次调用其next（）方法时返回列表的下一个元素。在

所以复杂性应该是：

初始化：O（1）

返回下一个元素：O（1）

返回所有元素：n*O（1）

请注意，enumerate不会创建新的数据结构（元组列表或类似的东西）！它只是在现有列表上迭代，并记住元素索引。在

你可以自己试试：

# 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 3

假设使用幼稚的方法（enumerate复制数组，然后迭代它），您有O（n）时间复制数组，然后O（n）时间迭代它。如果这仅仅是n而不是O（n），那么总共会有2*n的时间总量，但O（n）不是这样工作的；你所知道的是，所需的时间是一些的倍数。这基本上就是O（n）的意思，所以在任何情况下，枚举函数都是O（n）time total。在