在Python中从列表中弹出元素的时间复杂度是多少？
在Python中从列表中弹出元素的时间复杂度是多少？
提问于 2008-10-12 15:58:59
我想知道Python对象的pop方法(特别是CPython )的时间复杂度是多少。另外，list.pop(N)的N值是否会影响复杂性？
回答 2
Stack Overflow用户
回答已采纳
发布于 2008-10-12 16:15:39
最后一个元素的Pop()应该是O(1)，因为您只需要返回数组中最后一个元素引用的元素，并更新最后一个元素的索引。我期望任意元素的pop()为O(N)，并且平均需要N/2次操作，因为您需要将任何元素移出要在指针数组中向上移动一个位置的元素。
Stack Overflow用户
发布于 2018-07-29 07:58:12
它应该是O(1)与L.pop(-1)，O(n)与L.pop(0)
请参见以下示例：
from timeit import timeit
if __name__ == "__main__":
L = range(100000)
print timeit("L.pop(0)", setup="from __main__ import L", number=10000)
L = range(100000)
print timeit("L.pop(-1)", setup="from __main__ import L", number=10000)
>>> 0.291752411828
>>> 0.00161794329896页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/195625
复制相关文章
相似问题