请教大家一个问题 (转载) - Programming版

本页内容为未名空间相应帖子的节选和存档，一周内的贴子最多显示50字，超过一周显示500字访问原贴

Programming版 - 请教大家一个问题 (转载)

相关主题
● What's the efficient way to merge two BST?
● 请教双键的动态结构用什么数据结构比较好？
● 有什么方法可以优化hashtable？
● 弱弱的问问hash, hashtable? (转载)
● N个数字里面找出最大的5个数字的复杂度是什么？O(N)?
● 随机数与概率
● linked list vs Binary tree
● [合集] 一个数据结构问题
● one more c++ question
● 一道C＋＋面试编程题

相关话题的讨论汇总
话题: 问题话题: bst话题: linked话题: 改进话题: list

进入Programming版参与讨论

(共1页)

k**********a
发帖数: 255

【以下文字转载自 CS 讨论区】
发信人: kimulatakuya (木村拓哉), 信区: CS
标题: 请教大家一个问题
发信站: BBS 未名空间站 (Sat Sep 26 22:23:38 2009, 美东)
一个题目
有人试图改进哈希表具体做法是把hash到同一个bucket的元素用binary search tree
存储（经典的是用 linked list）他声称 insertion和lookup都有constant time
average performance
但是实际情况是对于N个element的hashtable 他的做法只有O(logN)的表现对于每个
操作
问题是他有什么错误呢如何改进呢
PS 我感觉如果BST不是balanced 那他用BST替代Linked list也没有用比如都是right
child的位置

(共1页)

进入Programming版参与讨论

相关主题
● 一道C＋＋面试编程题
● 有人能解释一下这段C++代码吗
● 帮帮看看这段tree insertion
● [合集] 如何得到一个指向STL元素的指针？
● 来来来,我也问个题 (转载)
● 关于C++中一个Class的大小 (转载)
● which is faster, table look up or bitwise operator?
● how to resolve this problem?
● [合集] 偶写的itoa
● [合集] 如何能让这个程序快一点呢？太慢了

相关话题的讨论汇总
话题: 问题话题: bst话题: linked话题: 改进话题: list

boards