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

发布于 2021-01-29 18:13:34

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

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

关注者
0
被浏览
172
1 个回答
  • 面试哥
    面试哥 2021-01-29
    为面试而生,有面试问题,就找面试哥。

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

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

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

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



知识点
面圈网VIP题库

面圈网VIP题库全新上线,海量真题题库资源。 90大类考试,超10万份考试真题开放下载啦

去下载看看