Big O表示法数组与链接表单插入

Question

Big O表示法数组与链接表单插入:

根据阵列的学术文献,它是常数O(1),对于链表,它是线性O(n).

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

没有在连续内存中布局的链表需要遍历.

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

Answer 1

O(1)准确地描述了在数组末尾的插入.但是,如果要插入数组的中间,则必须在该元素之后移动所有元素,因此在这种情况下插入的复杂性适用于O(n)数组.如果数组已满,则必须对数组进行大小调整.

对于链表,您必须遍历列表才能进行中间插入,这样就可以了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)