algorithm - 带有摊销常数或对数插入的列表 : how fast can possibly be lookup?

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

基于树的数据结构，如 rope或 finger tree , 通常可以在任意位置提供对数插入时间。取舍在于访问时间，访问时间往往也是对数的，除非在特殊情况下，例如手指树的末端。

Dynamic arrays可以在末端提供分摊常量插入，但在中间插入需要复制数组的一部分，并且时间复杂度为 O(N)，如您所述。

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

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

我怀疑没有人真正使用这样的数据结构的原因是，在中间插入很少是您最需要的情况，而对数插入(使用树)足以满足大多数现实世界的情况。