插入（在列表的末尾）是否具有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(?)

[根据Python Wiki中的TimeComplexity文章，append的平均情况为O（1），而insert的平均情况为O（n）。但是，在Python tutorial中提到：

...和a.insert（len（a），x）等同于a.append（x）。

我不确定这里的“等效”是指“功能上的等效”还是“时间复杂度上的等效”。谁能对此有所启发？

Answer 1

关于“功能等效”，我说这是真的，因为它们对于Python列表都会产生完全相同的结果。

时间复杂度，在这种情况下，它对于列表几乎是等效的，因为列表insert()实现是通过将元素移到索引后面来工作的，因此，如果将新元素插入到列表的末尾，则不会进行移位操作被执行。可以通过查看list insert的实现来验证。在插入执行行248-251中，>

for (i = n; --i >= where; )
        items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;
同时，在list append的实现中

Py_INCREF(v);
PyList_SET_ITEM(self, n, v);
[PyList_SET_ITEM为defined如：

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))
因此，由于where等于n（在这种情况下为列表大小），因此for循环立即终止。此后几行几乎是等效的，这基本上就是将元素插入数组中。 

Answer 2

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