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

Question

正如TimeComplexity文档中所见,Python的list类型实现使用数组.

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

Answer 1

它是摊销O(1),而不是O(1).

假设列表保留大小为8个元素,当空间用完时它的大小加倍.你想推50个元素.

前8个元素按O(1).第九个触发重新分配和8个副本,然后是O(1)推送.O(1)中的下一个7推.第17个触发重新分配和16个副本,然后是O(1)推送.接下来的15次推进O(1).第三十三个触发重新分配和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。