为什么添加到列表的前面需要二次时间？

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)]

为什么在这两种算法的Big O中存在如此明显的差异,唯一的区别是一个被添加到列表的前面而另一个被添加到列表的后面？

这对Java也适用吗？

Answer 1

因为列表针对追加进行了优化,而不是预先添加:如果您预先添加,则需要重新创建整个列表.

如果您想要一个可以在两端以相同效率附加的数据结构,请使用collections.deque.