在空 Python 列表中逐一追加“n”个元素的平均和最坏情况时间复杂度是多少？

Question

根据我的理解，Python列表使用动态数组作为底层数据结构。因此，当分配的内存未满时追加一个元素应该花费

O(1)

时间，但是当分配的内存已满时，它将在内存中分配几乎当前数组大小的两倍，然后创建数组的副本并追加元素，这应该需要

O(n)

时间，其中

是当前数组的大小。

我遇到了为什么Python的list.append()方法的时间复杂度是O(1)？其中讨论了追加单个元素的时间复杂度。

但是，如果我将

元素一一追加到空的 Python 列表中，时间复杂度是多少？

Answer 1

当您将“n”个元素逐一追加到空的 Python 列表中时，总体时间复杂度由这些单独追加操作的总和决定。

以下是此类情况的细分：

平均情况：由于动态数组实现，每个追加操作的平均情况时间复杂度为 O(1)，大多数情况下允许快速追加。因此，对于“n”个追加，平均时间复杂度为 O(n)。
最坏情况：最坏情况发生在每个追加操作触发内存重新分配并复制所有现有元素时。然而，由于内存分配大小呈几何级数（有时是指数级）增长，随着列表中元素数量的增加，重新分配的频率会降低。即使在最坏的情况下，这也会导致每个追加操作的摊余时间复杂度为 O(1)。因此，对于“n”次追加，最坏情况时间复杂度仍然是 O(n)。

这里的关键是摊销的概念，它将单个追加操作偶尔的 O(n) 成本分散到一系列 O(1) 追加操作上，从而导致每次追加的摊销成本为 O(1)手术。因此，在平均情况和最坏情况下（与创建长度为 n 的列表相同），逐一追加“n”个元素的总时间复杂度为 O(n)。