大O符号数组与链表插入

Question

大O符号数组与链表插入：

根据学术文献，对于数组，它是常数O(1)，对于链表，它是线性O(n)。

一个数组只需要一次乘法和加法。

未在连续内存中布局的链表需要遍历。

这个问题是，O(1)和O(n)是否分别准确地描述了数组和链表的索引/搜索成本？

Answer 1

O(1)准确地描述了数组末尾的插入。但是，如果要插入到数组的中间，则必须将该元素后面的所有元素移位，因此在这种情况下插入的复杂性对于数组来说是O(n)。End appending还不考虑如果数组已满则必须调整数组大小的情况。

对于链表，您必须遍历列表以执行中间插入，因此这就是O(n)。不过，您不必将元素向下移动。

维基百科上有一个很好的图表，上面有这样的内容：http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays

                          Linked list   Array   Dynamic array   Balanced tree

Indexing                          Θ(n)   Θ(1)       Θ(1)             Θ(log n)
Insert/delete at beginning        Θ(1)   N/A        Θ(n)             Θ(log n)
Insert/delete at end              Θ(1)   N/A        Θ(1) amortized   Θ(log n)
Insert/delete in middle     search time 
                                + Θ(1)   N/A        Θ(n)             Θ(log n)
Wasted space (average)            Θ(n)    0         Θ(n)[2]          Θ(n)

Answer 2

假设你正在谈论一个你已经知道插入点的插入，也就是说，这没有考虑到遍历列表以找到正确的位置：

数组中的插入取决于插入的位置，因为您将需要移动现有值。最坏的情况(插入数组)是O(x)。

在列表中插入是O(1)，因为您只需要修改相邻项的下一个/上一个指针。

Answer 3

我想数组的插入会慢一些。当然，你必须迭代一个链表，但是你必须分配、保存和释放内存才能插入到数组中。