algorithm - 具有摊销常数或对数插入的列表：查找速度有多快？

Question

每个人都知道（或必须知道），不可能设计一个同时支持 O(1) 中间插入和 O(1) 查找的列表数据结构。

例如，链表支持 O(1) 插入，但 O(N) 用于查找，而数组支持 O(1) 用于查找，但 O(N) 用于插入（可能摊销 O(1) 用于在开头插入，结束，或两者兼而有之）。

但是，假设您愿意用 O(1) 插入交换：

1. 摊销 O(1) 插入
2. O(log(N)) 插入

那么在每种情况下查找的理论界限是什么？你知道现有的数据结构吗？内存复杂度如何？

Answer 1

基于树的数据结构，如绳索或手指树，通常可以在任意位置提供对数插入时间。权衡是访问时间，除了在特殊情况下，例如手指树的末端，访问时间也往往是对数的。

动态数组可以在末端提供摊销常量插入，但在中间插入需要复制数组的一部分，并且时间为 O(N)，正如您所提到的。

可能实现一个支持摊销常量中间插入的数据结构。如果添加到任一端，则视为动态数组。如果在中间插入，请保留旧数组并在其“上方”添加一个新数组，其中包含列表的新“中间”，将旧数组用于中间左侧或右侧的数据。在您第一次中间插入之后，访问时间将是对数的，并且跟踪哪些数据在哪一层会很快变得复杂。

这可能是维基百科文章中提到的“分层”动态数组，我没有进一步研究。

我怀疑没有人真正使用这样的数据结构的原因是，在中间插入很少是您最需要的情况，而对数插入（使用树）对于大多数实际情况来说已经足够了。

Answer 2

这些仍然是悬而未决的问题，但我知道的最佳界限来自 Arne Andersson 的Sublogarithmic search without multiplications，其中包含 O(sqrt(lg(n))) 的插入、删除和查找。然而，这是以 2^k 额外空间为代价的，其中 k 是存储在数据结构中的整数的位数，因此我们仍然使用平衡二叉树而不是安德森的数据结构。数据结构的一个变体允许 O(1) 查找，但随后额外空间增加到 n2^k，其中 n 是数据结构中的元素数。随机变体不使用任何额外空间，但随后 sqrt(lg(n)) 插入/删除/查找时间变为平均空间时间，而不是最坏情况时间。