25
我想知道python中列表对象的弹出方法的时间复杂度（在CPython中）。 list.pop（N）的N的值是否影响复杂性？从Python中列表弹出元素的时间复杂度是多少？
A
回答
19
Pop()对于最后一个元素应该是O（1），因为您只需要返回数组中最后一个元素引用的元素并更新最后一个元素的索引。我期望pop()为一个任意元素为O（N）并且平均需要N/2个操作，因为您需要将指向数组中除去一个位置的元素之外的任何元素移出。
30
是的，这是O（1）到弹出Python列表的最后元件，和O（N）弹出一个任意元件（因为该列表的整个其余部分必须被移动）。
这里是Python的名单是如何存储和操纵一个伟大的文章：http://effbot.org/zone/python-list.htm
1
简短的回答是看这里：https://wiki.python.org/moin/TimeComplexity
不带任何参数弹出它的O（1）
随着自变量为：
- 平均时间复杂度O（k）（k表示传入的参数为 参数对流行
- 分期最坏情况下的时间复杂度为O（K）
- 最坏情况下的时间复杂度为O（n）
平均时间复杂度：
你把在任何时间值该操作的时间复杂度为O（nk）。
举例来说，如果你有9项列表不是从列表的末尾删除是9个操作，并从 开始移除列表1个操作（删除零指数和移动所有 其他元素到它们当前的索引 - 1）
由于列表的中间元素的n - k是k操作，所以平均值可以缩短为O（k）。
想想这个的另一种方法是想象每个索引从您的9个项目列表中删除一次。这将共有45项行动。 （n + 1）= 0（n + 1）+0（n + 1）+0（n + 1）得到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）时间。
我同意给出了答案，但对此的解释是错误恕我直言。您可以在O（1）时间从列表中删除任何对象（实质上使prev指针指向下一个，并将其删除）问题是，要在该位置查找对象，您需要遍历该列表点（需要O（N）时间，不需要平均值。）最后一个特例说明：pop（0）将取O（1），而不是O（0）。 – ntg 2017-12-11 10:07:43
@ntg列表是一个指针数组。要从中间的数组中移除一个指针，跟随它的所有指针必须在数组中移动一段时间，这个时间与列表的大小成正比（我们表示为N），因此是O（N） 。为了说明Big-O符号中的N不是被返回元素的索引，而是一个函数将O（1）算法的运行时间限定为常量时间 - 也就是说，它不依赖于大小列表。 O（N）表示边界函数是列表大小的常数倍，f（n）= c * n + b。 – tvanfosson 2017-12-11 16:38:39