哈希表的插入时间复杂度为 O(1)，但它们未排序。
BST 保持排序(可以使用前序遍历来遍历)，但插入时间复杂度为 O(logN)。
是否存在以下数据结构:
- 保证 O(1) 插入
- 维持元素的顺序？
如果不是，是否有证据证明这样的数据结构不存在？ 谢谢
最佳答案
在一般情况下，这样的数据结构是不可能的，因为您可以使用它来通过 O(n) 比较操作对序列进行排序，只需将序列元素逐一插入其中即可。很容易证明 Ω(n log n) 是 number of comparisons required to sort a list 的下界。 ，因此插入到“保持排序顺序”的数据结构中每个元素必须至少花费 Ω(log n) 时间。
这里我假设可以迭代数据结构以输出排序列表，而不进行任何额外的比较。如果仅仅需要额外的比较来迭代数据结构的内容，那么可以公平地说，数据结构在内部不“维护”排序顺序。如果您不介意花费 O(n log n) 时间来迭代大小为 n 的集合，那么您可以使用未排序的列表作为数据结构，插入时间为 O(1)。
关于data-structures - 是否有一种插入时间为 O(1) 且还能保持排序顺序的数据结构？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/66822548/