jav*_*red 4 algorithm data-structures
我可以有一个平均添加/删除操作为O(1)的集合(这对于基于哈希表的集合来说是典型的),最差的最大/最小值小于O(n),可能是O(log n)(典型的树 - 基础集)？
更新似乎在最简单的情况下,我可以在每次最大/最小消失时重新扫描所有N个元素,并且通常它给我O(1).但我将我的算法应用于股票交易,其中更接近最小/最大的变化更可能,所以我只是不想每次最大或最小消失时重新扫描所有内容,我需要比完全重新扫描更聪明的东西,它给出O(n).
upd2在我的情况下,set包含100-300个元素.最大/最小元素的变化很可能,因此max/min经常变化.我需要跟踪最大/分钟.我仍然想要添加/删除O(1).
这是一个不可能的结果,在确定性模型中最坏情况,非摊销边界的坏常数,其中密钥可以进行比较和散列,但没有别的.(是的,这是很多规定.我是第二个范Emde Boas树的推荐.)
通常情况下,比较下限,这是一个对手的论点.对手的游戏计划是插入许多键,同时有选择地删除算法信息最多的键.最终,算法将无法处理对max()的调用.
对手决定如下关键比对.与每个键相关联的是二进制字符串.每个键最初都有一个空字符串.当比较两个键时,它们的字符串被最小化地扩展,使得它们都不是另一个的前缀,并且根据字典顺序来确定比较.例如,使用键x,y,z,我们可以:
x < y: string(x) is now 0, string(y) is now 1
x < z: string(z) is now 1
y < z: string(y) is now 10, string(z) is now 11.
设k是一个操作所做的关键比较次数的最坏情况上限.每个密钥比较将总字符串长度增加最多两个,因此对于最多3*n个插入/删除操作的每个序列,总字符串长度最多为6*k*n.如果我们在有一个字符串长度至少为6*k的密钥时插入2*n个不同的带有散布删除的密钥,那么我们在去往至少有n个密钥的集合的路上最多删除n个密钥,其中每个密钥都有一个字符串短于6*k位.
将每个键的字符串任意扩展为6*k位.密钥字符串的(6*k)位前缀是密钥所属的桶.目前,该算法没有关于桶内密钥相对顺序的信息.有2**(6*k)个桶,我们想象按照(6*k)位前缀指示的递增顺序从左到右排列.对于足够大的n,存在具有常数(取决于k)键的分数和至少2*k倍于其右侧的组合桶的密钥的桶.删除后面的键,max()需要线性数量的额外比较来整理现在保持最大值的大桶,因为删除完成了所需工作的一半多一点.