大 O 表示法:数组 vs 链表插入:
根据学术文献,对于数组来说是常数 O(1),对于链表则是线性 O(n)。
一个数组只需要进行一次乘法和加法。
一个非连续内存的链表需要遍历。
这个问题是,是否准确地描述了数组和链表的索引/搜索成本分别为 O(1) 和 O(n)?
大 O 表示法:数组 vs 链表插入:
根据学术文献,对于数组来说是常数 O(1),对于链表则是线性 O(n)。
一个数组只需要进行一次乘法和加法。
一个非连续内存的链表需要遍历。
这个问题是,是否准确地描述了数组和链表的索引/搜索成本分别为 O(1) 和 O(n)?
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)
search time + O(1)
,其中搜索时间是遍历列表(大约为 O(n)
),插入是一个 O(1)
操作。 - wklO(1)
。 - bain假设您正在讨论一个已知插入点的插入操作,即这不考虑遍历列表以找到正确位置:
数组中的插入取决于插入位置,因为您需要移动现有值。最坏情况(在array[0]处插入)是O(x)。
在列表中插入的时间复杂度为O(1),因为您只需要修改相邻项的next/previous指针。
tldr 一个未排序的数组类似于一个集合。像集合一样,可以添加和删除元素,迭代和读取。但是,与集合一样,在特定位置插入元素是没有意义的,因为这样做就是试图强加一个排序顺序在定义上未排序的东西上。
一个数组被定义为未排序的(除非明确说明)。
数组的长度,即数组包含的元素数量,可以在O(1)时间内任意增加或减少,并且没有最大大小限制。
(在实际计算机中,由于诸如内存大小、虚拟内存、交换空间等各种因素,情况可能并非如此。但是对于算法渐近分析的目的而言,这些因素并不重要——我们关心算法的运行时间如何随着输入大小向无穷大增加而变化,而不是它在具有特定内存大小和操作系统的特定计算机上的表现。)
插入和删除是O(1),因为数组是一种未排序的数据结构。
插入不是赋值
Array.insert(Element e)
LinkedList.insert(Element e)
SortedArray.insert(Element e)
Array.insert(Element e, Index p)
通过这样的定义,调用者将覆盖数据结构的内部属性,并对未排序的数组施加排序约束 - 这种约束在数组的定义中不存在,因为数组是未排序的。
为什么这种误解会发生在数组而不是其他数据结构上?可能是因为程序员习惯使用赋值运算符来处理数组:
array[0] = 10
array[1] = 20
赋值运算符为数组的值提供了明确的顺序。需要注意的重要事项是,赋值与插入不同:
无序数组没有排序顺序,因此插入不需要允许覆盖位置。 插入与赋值不同。数组插入仅被定义为:
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)。
O(1)
。链表的大小取决于实现,但必须至少足够大以存储其所有元素。元素可以插入列表中的任何位置,并且找到相应的索引需要遍历。很久以前,在一台RAM比磁盘空间多的系统上,我实现了一个索引链表,它是手动输入或从磁盘加载时进行索引的。每个记录都附加到内存中的下一个索引中,磁盘文件打开记录附加到末尾关闭。
该程序在Model I Radio Shack计算机上缓存拍卖销售,并且对磁盘的写入仅用于防止电源故障和作为归档记录,因为为了满足时间限制,数据必须从RAM中获取并按相反的顺序打印,以便询问买家是否第一个出现的物品是他购买的最后一个物品。每个买家和卖家都与他们最后出售的物品相关联,而该物品与其之前的物品相关联。它只是一个单链接列表,从底部向上遍历。
通过反转条目进行更正。我为几件事使用了相同的方法,如果该方法适用于手头的工作并且索引保存到磁盘上,则我从未找到过更快的系统,而不必像在断电时重新加载文件时重建索引。
后来,我编写了一个更常规的编辑程序。它还可以重新组织数据,使其分组在一起。