CPython中list.insert(-1)固定索引插入的时间复杂度是多少？

问题背景 #

我编写了一段迭代构建列表的代码，所有插入操作均固定在倒数第二个位置，即调用list.insert(-1, value)。想知道在CPython实现中，该操作是否真的属于O(1)时间复杂度？同时对比两段功能等效的代码，它们的时间复杂度在CPython中是否相同？list.insert(-1, val)是否无论插入索引如何都会从头重建索引？

待分析代码 #

时间复杂度未知的实现 #

some_list = ['always first', 'always last']
for i in range(10000):
    some_list.insert(-1, 'value')

功能等效的O(1)时间复杂度实现 #

some_list = ['always first', 'always last']
for i in range(10000):
    last = some_list.pop()
    some_list.append('val')
    some_list.append(last)

解答 #

1. CPython中list.insert的底层逻辑 #

CPython的列表底层是动态数组实现的，插入操作的核心开销在于移动插入位置之后的元素，为新元素腾出空间：

• list.insert(k, val)会将索引k到末尾的所有元素向后移动一位，然后把val放到索引k的位置。
• 当调用insert(-1, val)时，等价于insert(len(some_list)-1, val)——也就是在倒数第二个位置插入。此时需要移动的元素只有最后一个元素（仅需把它从原位置挪到新的末尾），所以单次插入的移动开销是O(1)。

另外，insert操作并不会从头重建索引，它只操作插入位置之后的元素，不存在“从头重建”的逻辑。

2. 两段代码的时间复杂度对比 #

两段代码的均摊时间复杂度完全相同：

• 第二段代码中，pop()（从末尾删除）、append()（向末尾添加）都是O(1)操作，每次循环的总开销是O(1)。
• 第一段代码中，insert(-1, val)每次仅需移动1个元素，加上动态数组扩容的均摊开销也是O(1)，所以每次循环的总开销同样是O(1)。

唯一可能的差异是常数级别的开销：insert(-1)的底层实现会涉及少量额外的边界判断，而第二段代码的三次调用（pop+两次append）也有函数调用的开销，但这些都属于常数级差异，不影响时间复杂度的量级。

内容的提问来源于stack exchange，提问作者scotty-nukem