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

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

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

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

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

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