在列表末尾插入是否具有O(1)时间复杂度? [英] Does insert at the end of a list have O(1) time complexity?

问题描述

列表末尾的 append 和 insert 之间是否有区别?列表末尾的 insert 是恒定时间操作吗?

Is there a difference between append and insert at the end of a list? Is insert at the end of a list a constant time operation?

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教程中，提到了

According to the TimeComplexity article in the Python Wiki, the average case for append is O(1), while the average case for insert is O(n). However, in the Python tutorial, it is mentioned that:

...和 a.insert(len(a)，x)等效于 a.append(x).

我不确定是否等价"那里的意思是功能等效".或时间复杂度相当".有人知道吗?

I'm unsure if "equivalent" there means "equivalent in functionality" or "equivalent in time complexity". Does anyone know?

推荐答案

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

Regarding "equivalent in functionality", I'd say it is true since both of them will produce the exact same results for Python lists.

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

Time-complexity wise it is pretty much equivalent for list under such case, since the list insert() implementation works by shifting the elements behind the index, thus if the new element is inserted at the end of the list, no shifting operations is performed. This can be verified by looking at the implementation of the list insert. In the insertion implementation line 248-251,

for (i = n; --i >= where; )
        items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;

同时，在实现列表附加

Py_INCREF(v);
PyList_SET_ITEM(self, n, v);

其中 PyList_SET_ITEM 是定义为:

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))

因此，由于 where 等于 n (在这种情况下为列表大小)，因此for循环立即终止.此后几行几乎是等效的，基本上就是将元素插入数组.

Thus, since where equals n, which is the list size in this case, the for loop is terminated right away. Few lines after that are pretty much equivalent, which is basically just inserting the element into the array.

因此，可以说，在这种情况下，摊销的时间复杂度是相同的，即O(1)

Hence, it can be said that for this case the amortized time complexity is the same, which is O(1)

这篇关于在列表末尾插入是否具有O(1)时间复杂度?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！