python - 在列表末尾插入是否具有 O(1) 时间复杂度？

Question

append 和 insert 在列表末尾有区别吗？列表末尾的 insert 是常数时间操作吗？

nums = [1, 2, 3]
nums.append(4)  # Time complexity: O(1)
nums.insert(len(nums), 5)  # Time complexity: O(?)

根据TimeComplexity在 Python Wiki 的文章中，append 的平均情况是 O(1)，而 insert 的平均情况是 O(n)。然而，在 Python tutorial ，有人提到:

... and a.insert(len(a), x) is equivalent to a.append(x).

我不确定这里的“等效”是指“功能等效”还是“时间复杂度等效”。有人知道吗？

Answer 1

插入列表的最差时间复杂度是O(n-i)，其中n是列表的长度，i是索引您要插入的位置。

因此，如果您在最后一个索引处插入，则它会变成 O(1)。

这篇文章可能会帮助您更好地理解:

https://yourbasic.org/algorithms/time-complexity-arrays/ .