问题描述
如 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"部分案例".个别行动可能需要惊人的时间，这取决于容器的历史.
使用摊销分析，即使我们不得不偶尔执行昂贵的操作，我们也可以获得当您将它们视为一个序列而不是单独考虑时，平均"操作成本的下限.
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)?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！