在 Python 中从列表中弹出元素的时间复杂度是多少? [英] What is the time complexity of popping elements from list in Python?

问题描述

我想知道 Python 中列表对象的 pop 方法的时间复杂度是多少(尤其是在 CPython 中).list.pop(N) 的 N 值也会影响复杂性吗?

I wonder what is the time complexity of pop method of list objects in Python (in CPython particulary). Also does the value of N for list.pop(N) affects the complexity?

推荐答案

Pop() 最后一个元素应该是 O(1) 因为你只需要返回被引用的元素数组中的最后一个元素并更新最后一个元素的索引.我希望 pop() 对于任意元素是 O(N) 并且平均需要 N/2 次操作，因为您需要将任何元素移动到要删除一个位置的元素之外指针数组.

Pop() for the last element ought to be O(1) since you only need to return the element referred to by the last element in the array and update the index of the last element. I would expect pop() for an arbitrary element to be O(N) and require on average N/2 operations since you would need to move any elements beyond the element you are removing one position up in the array of pointers.

这篇关于在 Python 中从列表中弹出元素的时间复杂度是多少?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！