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

Question

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

因此，如果正在使用数组并且进行了一些附加操作，最终您将不得不重新分配空间并将所有信息复制到新空间。
毕竟，这是O（1）最坏的情况吗？

Answer 1

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

这些操作依赖于“最坏情况摊销”的“摊销”部分。根据容器的历史记录，各个动作可能会花费惊人的时间。

使用摊销分析，即使我们偶尔需要执行昂贵的操作，当您将其视为序列而不是单独进行操作时，我们也可以降低“平均”操作成本。

因此，任何单个操作都可能非常昂贵-O（n）或O（n ^ 2）或更大的值-但由于我们知道这些操作很少见，因此我们保证可以在内部执行一系列O（n）操作准时。