我刚找到这些 performance notes for cPython lists :
python 列表需要时间......
- ...获取或设置单个项目:O(1)
- ... 向列表添加一个项目:最差的 O(n^2)，但通常是 O(1)
- ...插入一个项目:O(n)，其中n是插入的元素之后的元素数
- ...删除一个项目:O(n)
现在我想知道 cPython 集的相同性能特征。另外，我想知道列表/集合的迭代速度有多快。我对大型列表/集合特别感兴趣。
请您参考如下方法:
据我所知，Python“规范”没有为列表、字典或集合的实现强加特定的数据结构，所以这不能“官方”回答。如果您只关心 CPython(引用实现)，那么我们可以加入一些非官方的复杂性。您可能想要重新表述您的问题以针对特定的 Python 实现。
无论如何，你说的复杂度都不对。假设一个动态调整大小的数组实现，附加一个项目被摊销 O(1) : 大多数情况下你只是简单地复制新值，在最坏的情况下，你需要重新分配，复制所有 n项目，加上新的。接下来，插入具有完全相同的最坏情况，因此它具有相同的复杂度上限，但在最好的情况下，它只会移动 k。项目，其中 k是插入位置之后的项目数。
