每个人都知道(或者必须知道),要设计一个既支持中间插入O(1)又支持O(1)查找的列表数据结构是不可能的。
例如,链接列表支持O(1)插入,但O(N)用于查找,而数组支持O(1)用于查找,而O(N)支持插入(可能是摊销O(1)用于开头、结尾或两者)。
但是,假设您愿意将O(1)插入与以下内容交换:
那么,在这些情况下,查找的理论界限是什么?你知道现有的数据结构吗?那么记忆的复杂性呢?
发布于 2013-06-20 04:20:56
这些仍然是未解决的问题,但我所知道的最好的界限来自Andersson的无乘法次对数搜索,它具有O的插入、删除和查找(sqrt(lg(N)。然而,这需要2^k的额外空间,其中k是存储在数据结构中的整数中的位数,因此我们仍然使用平衡的二叉树而不是Andersson的数据结构。数据结构的一个变体允许O(1)查找,但是附加空间增加到n2^k,其中n是数据结构中的元素数。随机变量不使用任何额外的空间,但是sqrt(lg(n))插入/删除/查找时间变成平均空间时间,而不是最坏的情况时间。
发布于 2013-06-20 04:28:12
基于树的数据结构,如绳或手指树,通常可以在任意位置提供对数插入时间.折衷是在访问时间,这往往也是对数,除非在特殊情况下,如手指树的末端。
动态阵列可以在末端提供分期的常量插入,但是中间的插入需要复制数组的一部分,正如您所提到的,O(N)是时间上的。
可能有可能实现支持摊销常数中间插入的数据结构。如果添加到任何一端,则将其视为动态数组。如果插入中间,则保留旧数组,并添加一个新数组“在上面”,它包含列表的新“中间”,使用旧数组对中间的左边或右边的数据进行处理。访问时间将是对数后,您的第一个中间插入,并保持跟踪哪些数据是在哪一层将很快变得复杂。
这可能是维基百科文章中提到的“分层”动态数组,我还没有进一步研究它。
我怀疑没有人真正使用这样的数据结构的原因是,插入中间的情况很少是您最需要的情况,而对数插入(使用树)对于大多数真实世界的情况来说已经足够好了。
https://stackoverflow.com/questions/17204849
复制相似问题