大 O 表示法：数组与链表插入的比较

Question

大 O 表示法：数组 vs 链表插入：

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

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

一个非连续内存的链表需要遍历。

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

- user656925

---

我想我面临的问题是，我需要快速复习数组、链表、树和哈希表在大O性能方面的知识，但信息在某种程度上受到限制，因为这本身就是一个领域。 - user656925

我不知道任何关于数据结构及其运行时间的综合评论，但以下是一些资源：http://en.wikibooks.org/wiki/Data_Structures/Tradeoffs 和 http://essays.hexapodia.net/datastructures/ - wkl

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)

- wkl

---

抱歉如果这个问题很愚蠢，但是图表中的例外是否包括在LinkedList中间添加元素呢？或者，正如我猜测的那样，删除与插入相同。两者都不需要移动元素，而且都需要遍历列表。 - Crowie

@Crowie - 它确实有，它是 search time + O(1)，其中搜索时间是遍历列表（大约为 O(n)），插入是一个 O(1) 操作。 - wkl

啊…是的，我太糊涂了。插入/删除与插入或删除相同。谢谢啦。 - Crowie

对于未排序的数组来说，在中间插入没有意义，这就是为什么学术文献不考虑该操作，而是认为数组插入始终是 O(1)。 - bain

Answer 2

假设您正在讨论一个已知插入点的插入操作，即这不考虑遍历列表以找到正确位置：

数组中的插入取决于插入位置，因为您需要移动现有值。最坏情况（在array[0]处插入）是O(x)。

在列表中插入的时间复杂度为O(1)，因为您只需要修改相邻项的next/previous指针。

- tinman

Answer 3

tldr 一个未排序的数组类似于一个集合。像集合一样，可以添加和删除元素，迭代和读取。但是，与集合一样，在特定位置插入元素是没有意义的，因为这样做就是试图强加一个排序顺序在定义上未排序的东西上。

---

根据学术文献，数组的时间复杂度是常数O(1)，而链表的时间复杂度是线性O(n)。值得理解的是，为什么学术文献将数组插入引用为O(1)。有几个概念需要理解：

• 一个数组被定义为未排序的（除非明确说明）。

• 数组的长度，即数组包含的元素数量，可以在O(1)时间内任意增加或减少，并且没有最大大小限制。

  （在实际计算机中，由于诸如内存大小、虚拟内存、交换空间等各种因素，情况可能并非如此。但是对于算法渐近分析的目的而言，这些因素并不重要——我们关心算法的运行时间如何随着输入大小向无穷大增加而变化，而不是它在具有特定内存大小和操作系统的特定计算机上的表现。）

• 插入和删除是O(1)，因为数组是一种未排序的数据结构。

• 插入不是赋值

考虑将元素添加到未排序的数据结构中实际意味着什么。由于没有定义的排序顺序，任何实际发生的顺序都是随意的，不重要。如果您从面向对象的API角度来考虑，方法签名可能如下所示：

Array.insert(Element e)

请注意，这与其他数据结构（如链表或排序数组）的插入方法相同：

LinkedList.insert(Element e)
SortedArray.insert(Element e)

在所有这些情况下，insert方法的调用者不指定插入的值存储在哪里 - 它是数据结构的内部细节。此外，对于排序或未排序的数据结构，调用者尝试在特定位置插入元素没有意义。对于（未排序的）链表，该列表根据定义是未排序的，因此排序顺序无关紧要。对于排序数组，插入操作将按定义在数组的特定点插入元素。

因此，定义数组插入操作没有意义：

Array.insert(Element e, Index p)

通过这样的定义，调用者将覆盖数据结构的内部属性，并对未排序的数组施加排序约束 - 这种约束在数组的定义中不存在，因为数组是未排序的。

为什么这种误解会发生在数组而不是其他数据结构上？可能是因为程序员习惯使用赋值运算符来处理数组：

array[0] = 10
array[1] = 20

赋值运算符为数组的值提供了明确的顺序。需要注意的重要事项是，赋值与插入不同：

• 插入：将给定值存储在数据结构中，而不修改现有元素。
• 无序插入：将给定值存储在数据结构中，而不修改现有元素，并且检索顺序不重要。
• 有序插入：将给定值存储在数据结构中，而不修改现有元素，并且检索顺序很重要。
• 分配 a[x] = v：用给定值v覆盖位置x中的现有数据。

无序数组没有排序顺序，因此插入不需要允许覆盖位置。 插入与赋值不同。数组插入仅被定义为：

Array.insert(v):    
    array.length = array.length + 1
    // in standard algorithmic notation, arrays are defined from 1..n not 0..n-1
    array[array.length] = v

这是O(1)。

- bain

Answer 4

数组的插入操作我想会更慢一些。确实，你需要迭代一个链表，但是你还需要为数组分配、保存和释放内存来进行插入操作。

- MGZero

Answer 5

你在参考哪些文献？数组的大小在创建时确定，并且以后永远不会改变。插入实际上只能发生在数组末尾的空闲槽中。任何其他类型的插入都可能需要重新调整大小，这肯定不是O(1)。链表的大小取决于实现，但必须至少足够大以存储其所有元素。元素可以插入列表中的任何位置，并且找到相应的索引需要遍历。

- Amir Afghani

---

在CLRS和其他计算机科学文献中，数组被定义为可以在常数时间内修改数组长度。显然，这并不适用于大多数编程语言，但这被认为是一种实现细节。 - bain

Answer 6

很久以前，在一台RAM比磁盘空间多的系统上，我实现了一个索引链表，它是手动输入或从磁盘加载时进行索引的。每个记录都附加到内存中的下一个索引中，磁盘文件打开记录附加到末尾关闭。

该程序在Model I Radio Shack计算机上缓存拍卖销售，并且对磁盘的写入仅用于防止电源故障和作为归档记录，因为为了满足时间限制，数据必须从RAM中获取并按相反的顺序打印，以便询问买家是否第一个出现的物品是他购买的最后一个物品。每个买家和卖家都与他们最后出售的物品相关联，而该物品与其之前的物品相关联。它只是一个单链接列表，从底部向上遍历。

通过反转条目进行更正。我为几件事使用了相同的方法，如果该方法适用于手头的工作并且索引保存到磁盘上，则我从未找到过更快的系统，而不必像在断电时重新加载文件时重建索引。

后来，我编写了一个更常规的编辑程序。它还可以重新组织数据，使其分组在一起。

- Gordon Couger