具有O（1）插入和O（log（n））搜索复杂性的数据结构？

Question

即使在最坏的情况下，是否有任何数据结构可以提供O（1）——即常数——插入复杂性和O（log（n））搜索复杂性？

排序后的向量可以进行O（log（n））搜索，但插入需要O（n）（考虑到我并不总是在前面或后面插入元素这一事实）。而列表可以进行O（1）插入，但不能提供O（log（n））查找。

我想知道这样的数据结构是否可以实现。

Answer 1

否（至少在一个模型中，存储在数据结构中的元素只能按顺序进行比较；哈希对最坏情况下的时间界限没有帮助，因为可能会发生一次大冲突）。

假设每个插入最多需要c比较。（见鬼，让我们假设n个插入最多需要c*n比较。）考虑一个插入n个元素然后查找一个元素的对手。我将描述一种对抗性策略，在插入阶段，该策略迫使数据结构包含Omega（n）元素，考虑到目前为止所做的比较，这些元素可以以任何方式排序。然后可以强制数据结构搜索这些元素，这相当于一个未排序的列表。结果是查找具有最坏情况下的运行时间ω（n）。

对手的目标是尽可能少地泄露信息。元素分为三组：赢家、输家和未知。最初，所有元素都在未知组中。当算法比较两个未知元素时，任意选择的一个元素成为赢家，另一个元素成为输家。胜利者被认为比失败者更伟大。类似地，未知输家、未知赢家和输家-赢家比较通过将其中一个元素指定为赢家，将另一个元素指定为输家来解决，而不更改现有的指定。剩下的案例是输家-输家和赢家-赢家比较，它们是递归处理的（因此赢家组有一个赢家未知子组、一个赢家-赢家子组和一个赢家-输家子组）。通过一个平均参数，因为至少n/2个元素在最多2*c的时间内进行比较，所以存在一个子集。。。大小至少为n/2/3^（2*c）=ω（n）的子群。可以验证，通过之前的比较，这些元素中没有一个是有序的。

Answer 2

我想知道这样的数据结构是否可以实现。

恐怕答案是否定的。

搜索确定，插入不

当我们观察二叉搜索树、B树、红黑树和AVL树等数据结构时，它们的平均搜索复杂度为O（log N），但同时平均插入复杂度与O（log N）相同。原因是显而易见的，搜索将遵循（或导航通过）插入发生的相同模式。

插入OK，搜索NOT

数据结构，如单向链表、双向链表的平均插入复杂度为O（1），但在单向链表和双向链表中搜索是痛苦的O（N），只是因为它们没有任何基于索引的元素访问支持。

您的问题的答案在于Skiplist实现，它是一个链表，但它平均需要插入O（logn）（当列表需要在O（1）中插入时）。

在结束语中，Hashmap非常接近于以巨大的空间代价来满足快速搜索和快速插入的要求，但是如果实现得很糟糕，它可能会导致插入和搜索的O（N）的复杂性。

Answer 3

是的，但是你必须在两个方面稍微改变规则：

1） 您可以使用具有O（1）插入和O（1）搜索的结构（例如CritBit树，也称为按位trie），并添加人工成本，将搜索转换为O（logn）。

比特树就像比特的二进制基数树。它通过沿着密钥的位（比如32位）移动来存储密钥，并使用该位来决定在每个节点上向左（“0”）还是向右（“1”）导航。搜索和插入的最大复杂度都是O（32），即O（1）。

2）我不确定这在严格的理论意义上是O（1），因为O（1）只有在我们限制值范围（比如32位或64位）时才起作用，但出于实际目的，这似乎是一个合理的限制。

请注意，在插入可能的密钥置换的重要部分之前，感知性能将为O（logn）。例如，对于16位密钥，您可能需要插入2^16=65563个密钥的重要部分。