Python中从列表中弹出元素的时间复杂度是多少？
我想知道在Python中，list对象的pop方法的时间复杂度是多少（特别是在CPython中）。另外，list.pop(N)中的N值会影响复杂度吗？
4 个回答
简单来说，可以看看这里：https://wiki.python.org/moin/TimeComplexity
如果没有参数传给pop操作，它的时间复杂度是O(1)，也就是很快。
如果给pop传了参数：
- 平均时间复杂度是O(k)（k代表你传给pop的参数值）
- 摊销最坏情况时间复杂度是O(k)
- 最坏情况时间复杂度是O(n)
平均时间复杂度：
每当你往列表里放一个值时，这个操作的时间复杂度是O(n - k)。
举个例子，如果你有一个包含9个元素的列表，从列表的末尾删除一个元素需要9次操作，而从开头删除一个元素只需要1次操作（就是删除第0个元素，然后把其他元素都往前移动一位）。
因为对于列表中间的元素，n - k是k次操作，所以平均可以简化为O(k)。
你也可以这样想：假设你从这个9个元素的列表中每个索引都删除了一次，总共会进行45次操作。（9+8+7+6+5+4+3+2+1 = 45）
45等于O(nk)，而因为pop操作进行了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)。
是的，从Python列表中删除最后一个元素的时间复杂度是O(1)，也就是说这个操作非常快。而如果你要删除列表中的某个任意元素，时间复杂度是O(N)，这意味着需要花费更多的时间，因为要把后面的所有元素都往前移动一位。
这里有一篇很棒的文章，讲解了Python列表是如何存储和操作的：http://effbot.org/zone/python-list.htm
对于最后一个元素的Pop()操作，应该是O(1)，因为你只需要返回数组中最后一个元素的值，并更新最后一个元素的索引就可以了。我认为对于任意元素的pop()操作是O(N)，平均需要N/2次操作，因为你需要把被删除元素后面的所有元素向前移动一个位置。