从其他编程语言到python的人经常会问他们应该如何预分配或初始化列表。对于来自Matlab的人来说尤其如此，其中代码为
l = []
for i = 1:100
l(end+1) = 1;
end
返回一个警告，明确建议您初始化列表。
在SO上有几个帖子解释(并通过测试显示)在python中不需要列表初始化。下面是一个值得讨论的好例子(但列表可能很长):在Python
中创建具有初始容量的列表然而，有一天，当我在寻找python的操作复杂度时，我在python官方wiki上偶然发现了这句话:
这似乎表明列表确实有预分配大小和超过该大小将导致整个列表移动。列表操作的最大[成本]来自超过当前分配大小(因为一切都必须移动)，
这动摇了我的基础。列表预分配能否降低代码的总体复杂性(就操作数量而言)?如果不是，那句话是什么意思?
编辑:
显然我的问题是关于(非常常见的)代码:
container = ... #some iterable with 1 gazilion elements
new_list = []
for x in container:
... #do whatever you want with x
new_list.append(x) #or something computed using x
在这种情况下，编译器无法知道container中有多少项，因此如果句子中所说的是真的，new_list可能需要他分配的内存进行大量更改。
我知道这对于列表推导式是不同的
列表预分配是否可以降低代码的总体复杂性(就操作数量而言)?
不，代码的总体时间复杂度是相同的，因为重新分配列表的时间成本是O(1)，分摊到所有增加列表大小的操作上。
如果不是，那句话是什么意思?
原则上，通过避免多次重新分配，预分配列表可以减少一些常数因子的运行时间。这并不意味着复杂性更低，但它可能意味着代码在实践中更快。如果有疑问，对代码的相关部分进行基准测试或概要分析，以比较这两种选择;在大多数情况下，这并不重要，当它发生时，无论如何都可能有更好的替代方案(例如NumPy数组)来实现相同的目标。
new_list可能会要求他分配的内存更改不可思议的次数
列表的重新分配遵循一个几何级数，所以如果列表的最终长度是n，那么列表在整个过程中只被重新分配O(logn)次;不是"不可思议的次数"。数学运算的方式是，无论列表有多大，每个元素被复制到一个新的底层数组的平均次数都是一个常数，因此，向列表添加元素的平摊成本为O(1)。