首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >有摊销常数或对数插入的列表:查找的速度可能有多快?

问有摊销常数或对数插入的列表:查找的速度可能有多快?
EN

Stack Overflow用户
提问于 2013-06-20 03:36:59
回答 2查看 375关注 0票数 4

每个人都知道(或者必须知道),要设计一个既支持中间插入O(1)又支持O(1)查找的列表数据结构是不可能的。

例如,链接列表支持O(1)插入,但O(N)用于查找,而数组支持O(1)用于查找,而O(N)支持插入(可能是摊销O(1)用于开头、结尾或两者)。

但是,假设您愿意将O(1)插入与以下内容交换:

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

那么,在这些情况下,查找的理论界限是什么?你知道现有的数据结构吗?那么记忆的复杂性呢?

EN

回答 2

Stack Overflow用户

回答已采纳

发布于 2013-06-20 04:20:56

这些仍然是未解决的问题,但我所知道的最好的界限来自Andersson的无乘法次对数搜索,它具有O的插入、删除和查找(sqrt(lg(N)。然而,这需要2^k的额外空间,其中k是存储在数据结构中的整数中的位数,因此我们仍然使用平衡的二叉树而不是Andersson的数据结构。数据结构的一个变体允许O(1)查找,但是附加空间增加到n2^k,其中n是数据结构中的元素数。随机变量不使用任何额外的空间,但是sqrt(lg(n))插入/删除/查找时间变成平均空间时间,而不是最坏的情况时间。

票数 2
EN

Stack Overflow用户

发布于 2013-06-20 04:28:12

基于树的数据结构,如绳或手指树,通常可以在任意位置提供对数插入时间.折衷是在访问时间,这往往也是对数,除非在特殊情况下,如手指树的末端。

动态阵列可以在末端提供分期的常量插入,但是中间的插入需要复制数组的一部分,正如您所提到的,O(N)是时间上的。

可能有可能实现支持摊销常数中间插入的数据结构。如果添加到任何一端,则将其视为动态数组。如果插入中间,则保留旧数组,并添加一个新数组“在上面”,它包含列表的新“中间”,使用旧数组对中间的左边或右边的数据进行处理。访问时间将是对数后,您的第一个中间插入,并保持跟踪哪些数据是在哪一层将很快变得复杂。

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

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

票数 3
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/17204849

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档