为什么在列表前面添加元素会花费二次时间？

Question

这个代码示例的复杂度是 O(N^2)

results = []

for i in range(1000000)
    result = [f(i)] + results

这个代码示例的复杂度是 O(N)

results = []

for i in range(1000000)
    result = results + [f(i)]

为什么这两个算法的复杂度差别这么大呢？唯一的不同就是一个是在列表的前面添加，而另一个是在列表的后面添加？

这种情况在 Java 中也适用吗？

Answer 1

之所以会这样，是因为CPython是用C语言写的，它用C语言的数组来存储列表的内容。当你想在列表的最前面添加一个元素时，必须先重新分配空间并移动已有的元素。

至于你问的第二个问题，“在Java中也是这样吗？”答案是肯定的，Java中的基本数组和ArrayList都不允许在列表前面添加元素，而不重新分配空间和移动元素。

另外，你的代码有问题，因为你把值赋给了result而不是results，所以实际上并没有导致问题中提到的性能下降。要更好地展示这个现象，可以用以下代码：

results = []
for i in range(1000000):
    results.insert(0, f(i))

还有一个追加版本：

results = []
for i in range(1000000):
    results.append(f(i))

或者使用timeit模块：

$ python -m timeit 'results = []' 'for i in range(10000): results.insert(0, i)'
10 loops, best of 3: 50.9 msec per loop
$ python -m timeit 'results = []' 'for i in range(10000): results.append(i)'
1000 loops, best of 3: 794 usec per loop

Answer 2

因为列表是为了快速添加元素到末尾而优化的，而不是在开头添加。如果你在开头添加元素，整个列表就得重新创建一遍。

如果你想要一个可以在两端都能高效添加元素的数据结构，可以使用 collections.deque。