python - 为什么 l.insert(0, i) 在 python 中比 l.append(i) 慢？

Question

我测试了两种在 python 中反转列表的不同方法。

import timeit

value = [i for i in range(100)]
def rev1():
    v = []
    for i in value:
        v.append(i)
    v.reverse()

def rev2():
    v = []
    for i in value:
        v.insert(0, i)

print timeit.timeit(rev1)
print timeit.timeit(rev2)

有趣的是，将值插入第一个元素的第二种方法比第一种方法慢得多。

20.4851300716
73.5116429329

这是为什么？从操作上来说，在头部插入一个元素似乎并没有那么昂贵。

Answer 1

insert是一个 O(n)操作，因为它要求插入位置处或插入位置之后的所有元素向上移动一个。 append , 另一方面，通常是 O(1) (和 O(n) 在最坏的情况下，必须分配更多空间)。这解释了巨大的时差。

这些方法的时间复杂度已被详细记录 here .

我引用:

Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move).

现在，回到您的代码，我们可以看到 rev1()是一个 O(n)实现而rev2()实际上是O(n<sup>2</sup>) , 所以 rev2() 是有道理的会慢很多。