列出与分期常量或对数插入：如何快速可能被查找？ [英] List with amortized constant or logarithmic insertion: how fast can possibly be lookup?
问题描述
大家都知道（或应该知道），这是不可能设计，同时支持O（1）插入中间的列表数据结构和O（1）查找。
Everybody knows (or must know), that it is impossible to design a list data structure that supports both O(1) insertion in the middle, and O(1) lookup.
例如，链表的支持O（1）插入，但O（N）进行查找，而阵列的支持O（1）查找，但O（N），用于插入（可能摊余O（1）插入在开始，结束，或两者）。
For instance, linked list support O(1) insertion, but O(N) for lookup, while arrays support O(1) for lookup, but O(N) for insertion (possibly amortized O(1) for insertion at the beginning, the end, or both).
但是，假设你是愿意与交易O（1）插入：
However, suppose you are willing to trade O(1) insertion with:
- 在摊销O（1）插入
- O（日志（N））插入
那么什么是理论界查找在每种情况？你知不知道现有的数据结构？那么内存的复杂性？
Then what is the theoretical bound for lookup in each of these cases? Do you know existing data structures? What about memory complexity?
推荐答案
这些仍然是开放的问题，但我知道的最好的范围是从阿恩·安德森的的 Sublogarithmic搜索无乘法的，其中有插入，删除，并查找的O（开方（LG（N）））。然而，这是以2 ^ K个追加的空间，其中，k是被存储在数据结构中的整数的比特数，因此，我们仍然使用平衡二叉树代替Andersson的数据结构的原因成本。该数据结构的变体允许O（1）查找，但随后的额外的空间增大到n2 ^ k其中n是在该数据结构的元素数。随机变量不使用任何额外的空间，但随后的sqrt（LG（N））的插入/删除/查找时间成为船舶平均舱位倍，而不是最坏情况下时间。
These are still open problems, but the best bounds that I am aware of are from Arne Andersson's Sublogarithmic searching without multiplications, which has insertions, deletions, and lookups of O(sqrt(lg(n))). However, this comes at a cost of 2^k additional space, where k is the number of bits in the integers being stored in the data structure, hence the reason that we're still using balanced binary trees instead of Andersson's data structure. A variant of the data structure allows O(1) lookups, but then the additional space increases to n2^k where n is the number of elements in the data structure. A randomized variant doesn't use any additional space, but then the sqrt(lg(n)) insertion/deletion/lookup times become average space times instead of worst case times.
这篇关于列出与分期常量或对数插入：如何快速可能被查找？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
