Python列表实现栈的时间复杂度及相关技术疑问解析

关于list.append()和list.pop()的时间复杂度 #

首先明确：Python列表末尾的append()和pop()（不带参数，即弹出最后一个元素）均为摊还O(1)，而非O(n)。

你看到的“pop()为O(n)”的说法，大概率指的是弹出列表开头元素（list.pop(0)）——因为动态数组要把后面所有元素往前挪一位，这时候时间复杂度才是O(n)。但栈的操作只涉及末尾，完全不需要考虑这种情况。

关于摊还时间复杂度：动态数组扩容时确实会触发O(n)的元素复制，但这种扩容操作是摊还到多次O(1)操作上的。Python列表的扩容策略是每次将容量翻倍（不同版本可能有微调，但核心是倍数扩容），所以每k次append操作才会触发一次扩容，总耗时平均下来，每次append的摊还成本还是O(1)。pop()操作如果只是弹出末尾元素，除非触发缩容（部分实现会在元素过少时缩小容量），但同样缩容的摊还成本也是O(1)，不影响整体栈操作的时间复杂度。

关于动态数组扩容的内存分配与复制耗时 #

内存分配和元素复制是两个独立的步骤，各自会产生耗时：

• 内存分配：向操作系统申请一块新的、更大的连续内存空间，这个过程的耗时取决于操作系统的内存管理机制，通常是常数级或接近常数的操作（比如依赖操作系统预分配的内存池优化），但本质上和元素复制是分开的。
• 元素复制：把原数组中的所有元素逐个拷贝到新的内存空间，这一步的时间复杂度是O(n)，因为要遍历所有元素。

实际运行中这两个步骤会连续执行，看起来像一个整体操作，但从底层原理和耗时来源上，它们是分开的。内存分配的额外耗时通常远小于元素复制的耗时，所以分析时间复杂度时，主要关注O(n)的复制操作，内存分配的成本可忽略不计——因为它不随元素数量n线性增长。

内容的提问来源于stack exchange，提问作者sonaeteiru22