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

我想知道 Python (尤其是 CPython)中的 pop 列表对象方法的时间复杂度是多少。另外，list.pop (N)的 N 值是否会影响复杂性？

73869 次浏览
小开
最佳答案

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

小开

是的，弹出 Python 列表中的 最后元素是 O (1) ，弹出 随心所欲元素是 O (N)(因为必须移动列表的其余部分)。

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

小开

简短的回答是看这里: https://wiki.python.org/moin/TimeComplexity

没有参数弹出它的 O (1)

有一个很流行的说法:

  • 平均时间复杂度 O (k)(k 表示作为 支持流行音乐的论据
  • 分摊最坏情况时间复杂度 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)乘以 n 除以 nk 得到 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)时间。

以下是我写的一些想法，以防有所帮助:

小开

L. pop (- 1)应该是 O (1) ，L. pop (0)应该是 O (n)

请参阅以下例子:

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

提交答案