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

Question

从TimeComplexity的文档中可以看出，Python 的list类型是使用数组实现的。

因此，如果正在使用一个数组并且我们进行了一些附加操作，最终您将不得不重新分配空间并将所有信息复制到新空间。
毕竟，它怎么可能是 O(1) 最坏的情况？

Answer 1

它是摊销 O(1)，而不是 O(1)。

假设列表保留大小是 8 个元素，当空间用完时它的大小会翻倍。你想推送 50 个元素。

前 8 个元素压入 O(1)。第 9 个触发重新分配和 8 个副本，然后是 O(1) 推送。接下来的 7 推入 O(1)。第十七次触发重新分配和 16 个副本，然后是 O(1) 推送。接下来的 15 次推入 O(1)。第 33 次触发重新分配和 32 个副本，然后是 O(1) 推送。接下来的 17 推入 O(1)。

所以所有的推送都有 O(1) 复杂度，我们在 O(1) 有 56 个副本，在 O(n) 有 3 个重新分配，n = 8、16 和 32。请注意，这是一个几何级数并且渐近等于 O(n)，其中 n = 列表的最终大小。这意味着将 n 个对象推入列表的整个操作是 O(n)。如果我们对每个元素进行摊销，则为 O(n)/n = O(1)。

Answer 2

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

这些操作依赖于“摊销最坏情况”的“摊销”部分。取决于容器的历史，单个操作可能需要非常长的时间。

使用摊销分析，即使我们必须偶尔执行昂贵的操作，当您将它们视为一个序列而不是单独考虑时，我们也可以获得“平均”操作成本的下限。

因此，任何单独的操作都可能非常昂贵 - O(n) 或 O(n^2) 或更大的东西 - 但由于我们知道这些操作很少见，我们保证可以完成一系列 O(n) 操作准时。

Answer 3

这很容易。

我们可以通过累计将 n 个元素附加到一个数组列表中的总时间并将其除以 n 来计算这一点。

首先，我们需要重定位 log(n) 次，每次重定位都加倍 2。所以我们有一个比例序列，比例为 2，长度为 log(n)。

比例级数之和为a(1-r^n)/(1-r) 所以重定位的总时间为(1-n)/(1-2)=n 时间复杂度为n/n= 1.