Python中从列表中弹出元素的时间复杂度是多少？

我想知道Python中列表对象的pop方法的时间复杂度是什么(特别是在CPython中).list.pop(N)的N值也会影响复杂性吗？

1> Dan Lenski..：

---

是的,弹出Python列表的最后一个元素是O(1),弹出任意元素是O(N)(因为必须移动列表的其余部分).

这是一篇关于如何存储和操作Python列表的精彩文章:http://effbot.org/zone/python-list.htm

---

所以为了说清楚,list.pop(0)是O(n)而list.pop()是O(1).

---

要同时在O（1）中进行这两种操作，请使用collections.deque参见[here]（https://wiki.python.org/moin/TimeComplexity）

2> tvanfosson..：

---

Pop()因为你只需要返回数组中最后一个元素引用的元素并更新最后一个元素的索引,因此最后一个元素应该是O(1).我希望pop()任意元素为O(N)并且需要平均N/2次操作,因为你需要移动任何元素超出你在指针数组中移除一个位置的元素.

3> Gwater17..：

---

简短的答案是在这里：https : //wiki.python.org/moin/TimeComplexity

没有参数弹出其O（1）

弹出一个参数：

平均时间复杂度O（k）（k表示作为pop参数传入的数字

摊销最坏情况时间复杂度O（k）

最坏情况下的时间复杂度O（n）

平均时间复杂度：

每当您输入一个值时，该操作的时间复杂度为O（n-k）。

例如，如果您有9个项目的列表，则从列表末尾删除是9个操作，而从列表开头删除是1个操作（删除第0个索引并将所有其他元素移动到它们的当前索引-1 ）

由于列表中间元素的n-k为k次运算，因此平均值可以缩短为O（k）。

考虑这种情况的另一种方法是，想象每个索引都从9个项目列表中删除一次。总共将进行45次操作。（9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45）

45等于O（nk），并且由于弹出操作发生了O（n）次，因此您将nk除以n得到O（k）

摊销最坏情况时间复杂度

假设您再次列出了9件商品。假设您要删除列表中的每个项目，并且发生最坏的情况，并且每次都删除列表中的第一项。

由于列表每次缩小1，因此每次操作总数从9减少到1。

9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 +1 = 45.45等于O（nk）。由于您进行了9次运算，而9为O（n）来计算摊销的最坏情况，因此您进行的O（nk）/ O（n）等于O（k）

指出平均和摊销的最坏情况下的时间复杂度为O（n）也是正确的。请注意，O（k）大约为O（1 / 2n），并且减去常数等于O（n）

最坏情况下的时间复杂度

与摊销最坏情况下的时间复杂度不同，您不必考虑数据结构的状态，而只考虑任何单个操作的最坏情况。

在这种情况下，最坏的情况是您必须从列表中删除时间为O（n）的第一项。

如果有帮助，请考虑以下几点：