为什么pop()的大O与python中的pop(0)不同 [英] Why is the big O of pop() different from pop(0) in python

问题描述

它们都不应该都是O(1)，因为从Python列表中的任何位置弹出元素都会涉及破坏该列表并在新的内存位置创建一个列表吗?

Shouldn't they both be O(1), as popping an element from any location in a Python list involves destroying that list and creating one at a new memory location?

推荐答案

Python的list实现在幕后使用动态调整大小的C array，通常 元素的删除要求您在以下位置移动元素之后，以防止出现缝隙.

Python's list implementation uses a dynamically resized C array under the hood, removing elements usually requires you to move elements following after up to prevent gaps.

list.pop()会删除 last 元素.可以在固定时间内完成对该元素的访问.之后没有任何元素，因此无需进行任何更改.

list.pop() with no arguments removes the last element. Accessing that element can be done in constant time. There are no elements following so nothing needs to be shifted.

list.pop(0)删除 first 元素. 所有剩余元素必须上移一级，这样才能花费O(n)线性时间.

list.pop(0) removes the first element. All remaining elements have to be shifted up one step, so that takes O(n) linear time.

这篇关于为什么pop()的大O与python中的pop(0)不同的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！