大O符号数组与链接列表插入 [英] Big O Notation Arrays vs. Linked List insertions

问题描述

根据阵列的学术文献，它是常数O（1），对于链接列表，它是线性O（

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

没有布置的链接列表在连续的内存中需要遍历。

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

解决方案

O（1）准确描述插入数组的末尾。但是，如果要插入到数组的中间，则必须在元素之后移动所有元素，因此在这种情况下插入的复杂度为 O（n）用于数组。对于链接列表，您必须遍历列表以进行中间插入，因此，结束附加也可以折扣您必须调整数组的大小（如果已满）的情况。

这是 O（n）。你不需要移动元素。

维基百科有一个很好的图表： http://en.wikipedia.org/wiki/Linked_list#Linked_lists_vs._dynamic_arrays

 链接列表数组动态数组平衡树
 
索引Θ（n）Θ（1）Θ（1）Θ（log n）
开始时插入/删除Θ（1） N / AΘ（n）Θ（log n）
在结尾插入/删除Θ（1）N / AΘ（1）摊销Θ（log n）
在中间搜索时间插入/删除
 +Θ（1）N / AΘ（n）Θ（log n）
废弃空间（平均）Θ（n）0Θ（n）[2]Θ（n）
  

Big O Notation Arrays vs. Linked List insertions:

According to academic literature for arrays it is constant O(1) and for Linked Lists it is linear O(n).

An array only takes one multiplication and addition.

A linked list which is not laid out in contiguous memory requires traversal.

This question is, does O(1) and O(n) accurately describe indexing/search costs for arrays and linked lists respectively?

解决方案

O(1) accurately describes inserting at the end of the array. However, if you're inserting into the middle of an array, you have to shift all the elements after that element, so the complexity for insertion in that case is O(n) for arrays. End appending also discounts the case where you'd have to resize an array if it's full.

For linked list, you have to traverse the list to do middle insertions, so that's O(n). You don't have to shift elements down though.

There's a nice chart on wikipedia with this: 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)

这篇关于大O符号数组与链接列表插入的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！