为什么pop()中的大O与python中的pop(0)不同

它们不应该是O(1),因为从Python列表中的任何位置弹出一个元素涉及销毁该列表并在新的内存位置创建一个？

Python的list实现array在引擎盖下使用动态调整大小的C ,删除元素通常需要您在向后移动元素以防止间隙.

list.pop()没有参数删除最后一个元素.访问该元素可以在恒定的时间内完成.没有元素跟随,所以没有什么需要转移.

list.pop(0)删除第一个元素.所有剩余的元素必须向上移动一步,因此需要O(n)线性时间.