TreeSet 中有序操作的时间复杂度是多少?
What is the time complexity of the following operations in java.util.TreeSet
?
first()
last()
lower()
higher()
I would assume that these are constant time but the API makes no guarantees.
如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。
发布评论
评论(5)
梦言归人2024-10-27 11:49:04
根据 TreeSet 默认使用的 TreeMap 的实现(sun jdk 1.6.0_23),看起来first()和last()都是O(log n)而不是O(1):
/**
* Returns the first Entry in the TreeMap (according to the TreeMap's
* key-sort function). Returns null if the TreeMap is empty.
*/
final Entry<K,V> getFirstEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.left != null)
p = p.left;
return p;
}
/**
* Returns the last Entry in the TreeMap (according to the TreeMap's
* key-sort function). Returns null if the TreeMap is empty.
*/
final Entry<K,V> getLastEntry() {
Entry<K,V> p = root;
if (p != null)
while (p.right != null)
p = p.right;
return p;
}
清引2024-10-27 11:49:04
其实我查了一下源码
在 http://developer.classpath.org/doc/java/util/ TreeSet-source.html,first()调用maps.firstKey()
然后在
http://developer.classpath.org/doc/java/util/TreeMap -source.html
393: public K firstKey()
394: (
395: if (root == nil)
396: throw new NoSuchElementException();
397: return firstNode().key;
398: )
并在firstNode()中,它执行while循环一直到左边
952: final Node<K, V> firstNode()
953: (
954: // Exploit fact that nil.left == nil.
955: Node node = root;
956: while (node.left != nil)
957: node = node.left;
958: return node;
959: )
~没有更多了~
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
实际上,我原以为这些操作对于一般实现来说都是
O(logN)
。要使
first()
和last()
的时间复杂度为O(1)
,TreeSet 实现需要维护一个指向最左边的指针和树中最右边的叶节点。维护这些会为每次插入增加恒定成本,并且至少为每次删除增加恒定成本。实际上,该实现可能会动态找到最左/最右节点...这是一个O(logN)
操作。lower()
和higher()
方法必须执行与get
相同的工作,因此O(logN )
。当然,您可以自己检查源代码,看看实际发生了什么。 (正如其他人所做的那样:见下文。)
Actually, I'd have thought that those operations are all going to be
O(logN)
for a general implementation.For
first()
andlast()
to beO(1)
the TreeSet implementation would need to maintain a pointer to the leftmost and rightmost leaf nodes in the tree respectively. Maintaining these adds a constant cost to every insertion and at least a constant cost to every deletion. In reality, the implementation will probably find the left / rightmost nodes on the fly ... which is anO(logN)
operation.The
lower()
andhigher()
methods have to do the same work asget
and are thereforeO(logN)
.Of course, you can check the source-code yourself to see what actually happens. (As other people have done: see below.)