为什么python的list.append()方法的时间复杂度是O(1)? [英] Why is the time complexity of python's list.append() method O(1)?

问题描述

如 TimeComplexity 的文档所示，Python 的 list 类型使用数组实现.

As seen in the documentation for TimeComplexity, Python's list type is implemented is using an array.

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

So if an array is being used and we do a few appends, eventually you will have to reallocate space and copy all the information to the new space.
After all that, how can it be O(1) worst case ?

推荐答案

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

If you look at the footnote in the document you linked, you can see that they include a caveat:

这些操作依赖于Amortized Worst"的Amortized"部分案例".个别行动可能需要惊人的时间，这取决于容器的历史.

These operations rely on the "Amortized" part of "Amortized Worst Case". Individual actions may take surprisingly long, depending on the history of the container.

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

Using amortized analysis, even if we have to occasionally perform expensive operations, we can get a lower bound on the 'average' cost of operations when you consider them as a sequence, instead of individually.

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

So, any individual operation could be very expensive - O(n) or O(n^2) or something even bigger - but since we know these operations are rare, we guarantee that a sequence of O(n) operations can be done in O(n) time.

这篇关于为什么python的list.append()方法的时间复杂度是O(1)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！