寻找一种支持随机访问和删除的高效索引数据结构

Question

我想我偶然发现了一种新颖的数据结构。

是否存在一种可以在特定索引处添加和删除元素的方法，既高效又有效（优于线性时间）？不要求结构中的元素按其顺序进行索引。例如，元素可以存储为 5, 2, 8, 1, 3, 3。DataStructure[2] 将给出 8，del DataStructure[2] 将删除 8。

Answer 1

我认为不存在可以在特定索引处添加和删除元素的数据结构，两者都有效（比线性时间更好）。以下是一些流行的数据结构：

1。数组/向量：

• 插入和删除：

  O(n)

• 随机访问：

  O(1)

• 因此在特定索引处插入和删除元素的时间复杂度是

  O(1)+O(n)=O(n)

  。

2。链接列表：

• 插入和删除：

  O(1)

• 随机访问：

  O(n)

• 因此在特定索引处插入和删除元素的时间复杂度也是

  O(n)+O(1)=O(n)

  。

3.套装：

• 有序集：您只能存储已排序且唯一的数字数组（例如

  [1,2,3,5,8]

  ，而不是

  [5,2,8,1,3,3]

  ）。
• 无序集合：无法存储数组中数字的顺序。

4。地图：

• 有序映射：插入和删除：

  O(log(n))

  和索引

  k

  的随机访问：

  O(k*log(n))

  。如果您有一个以

  float

  作为键的有序地图，例如：

  {1.0:5, 2.0:2, 3.0:8, 4.0:1, 5.0:3, 6.0:3}

  ，并且您想要插入

  10

  作为索引

  k

  （成本

  O(log(n))

  ，您可以将

  {k_index:10}

  插入到地图中，其中

  k_index

  是数字索引

  k-1

  的键和索引

  k

  之间的数字（成本

  O(k*log(n))

  。总时间复杂度：

  O(k*log(n))

  。如果

  k < n/log(n)

  或

  k << n

  那么时间复杂度会更好比

  O(n)

  。
• 无序映射：插入和删除：

  O(1)

  和随机访问：

  O(n*log(n))

  （您必须按索引缩短无序映射的元素（在能够随机访问之前花费

  O(n*log(n))

  ）。类似于有序映射，但总时间复杂性是

  O(n*log(n))

  。