Python中列表操作的时间复杂度疑问

嗨，我来帮你把这个时间复杂度的问题掰扯明白～

首先得先搞清楚Python里的列表（List）本质是动态数组，背后是一块连续的内存空间，这是理解所有时间复杂度的核心。

为什么访问/修改任意索引的元素是O(1)？ #

因为数组的内存是连续的，每个元素的内存地址可以通过「数组起始地址 + 索引 × 单个元素占用的内存大小」直接计算出来。不管你要找的是第0个元素还是第1000个元素，这个计算都是一步到位的，不需要遍历其他元素，所以时间复杂度是常数级的O(1)。

为什么任意位置增删元素是O(n)？ #

没错，这确实和重新索引、元素挪动有关。比如你在列表中间某个位置插入元素：

• 插入位置后面的所有元素都得往后“挪一位”，给新元素腾出空间；
• 如果是删除元素，后面的所有元素都得往前“挪一位”，填补删除后留下的空缺。

最坏情况是在列表的第一个位置增删，这时候需要挪动整个列表的所有元素，所以时间复杂度是线性的O(n)。

那列表末尾的增删是不是O(1)？ #

完全正确！

• 末尾添加元素（append()）：Python列表会预先分配比当前实际元素数更多的内存空间（叫「超额分配」），只要还有剩余空间，直接把新元素放到末尾就行，不需要挪动任何元素，这时候是O(1)。当然如果预先分配的空间用完了，就需要申请一块更大的内存，把原来的元素全部复制过去，这一步是O(n)，但这种情况是「均摊」到多次操作上的，大部分时候append()都是O(1)。
• 末尾删除元素（pop()不带参数）：直接标记最后一个位置为可用，不需要挪动任何元素，所以肯定是O(1)。

备注：内容来源于stack exchange，提问作者rarara