Python的list.append()方法的时间复杂度为什么是O(1)？

Question

如 时间复杂度 文档所述，Python 的 list 类型是使用数组实现的。因此，如果正在使用数组并进行了几次附加操作，最终将不得不重新分配空间并将所有信息复制到新空间中。但是，它是如何实现 O(1) 最坏情况的？

- ohad edelstain

---

http://cs.stackexchange.com/questions/9380/why-is-push-back-in-c-vectors-constant-amortized - rlbond

Answer 1

这是摊还复杂度O(1)，而不是O(1)。

假设列表的保留大小为8个元素，当空间用尽时它会增加一倍。你要添加50个元素。

前8个元素的推入复杂度为O(1)。 第9个触发了重新分配和8次复制，然后是O(1)的推入。 接下来的7个元素的推入复杂度为O(1)。 第17个触发了重新分配和16次复制，然后是O(1)的推入。 接下来的15个元素的推入复杂度为O(1)。 第33个触发了重新分配和32次复制，然后是O(1)的推入。 接下来的31个元素的推入复杂度为O(1)。这将持续下去，直到在添加第65个、第129个、第257个元素等时，列表的大小再次加倍。

因此所有的推入操作都具有O(1)的复杂度，我们进行了64次O(1)的复制，以及3次O(n)的重新分配，其中n = 8、16和32。请注意，这是一个几何级数，并且渐近地等于O(n)，其中n为列表的最终大小。这意味着将n个对象推入列表的整个操作的复杂度为O(n)。如果我们将其摊分到每个元素上，那么就是O(n)/n = O(1)。

- rlbond

Answer 2

如果您查看所链接文档中的脚注，您会发现他们包含了一个警告：

这些操作依赖于“平摊”部分的“平摊最坏情况”。具体操作可能需要花费意外长的时间，这取决于容器的历史记录。

通过平摊分析，即使我们偶尔需要执行昂贵的操作，当将它们视为序列而不是单独考虑时，我们也可以获得对操作'平均'成本的下限估计。

因此，任何单个操作都可能非常昂贵- O(n)或O(n^2)或甚至更大-但由于我们知道这些操作很少发生，我们保证O(n)操作序列可以在O(n)时间内完成。

- Jacob Ritchie

---

我理解你在这里提供的链接，但这意味着“摊销最坏情况”实际上是“摊销平均情况”，因为如果每次进行n个追加操作时，你需要进行大量的分配和复制，这意味着你对于每个追加操作的平均时间复杂度是o(1)，而最坏情况下的时间复杂度是o(n)。 - ohad edelstain

不，摊销平均和摊销最坏情况是有区别的。摊销平均情况指的是序列的平均运行时间除以序列中的操作数。而摊销最坏情况是序列可能的最坏运行时间除以序列中的操作数。（可以看到，“平均”一词在两个不同的方面被使用，这有点令人困惑。） - Jacob Ritchie

您IP地址为143.198.54.68，由于运营成本限制，当前对于免费用户的使用频率限制为每个IP每72小时10次对话，如需解除限制，请点击左下角设置图标按钮（手机用户先点击左上角菜单按钮）。 - Jacob Ritchie

Answer 3

这很简单。

我们可以通过累加将n个元素添加到arraylist中所需的总时间并将其除以n来计算。

首先，我们需要重新定位log(n)次，每次重新定位都会增加2倍。因此，我们有一个比例系列，其比率为2，长度为log(n)。

比例级数的总和为a(1-r^n)/(1-r)。 因此，重新定位的总时间为(1-n)/(1-2)=n。 时间复杂度将是n/n=1。

- Isaac Chou