Java中TreeSet方法的计算复杂性 [英] Computational Complexity of TreeSet methods in Java

问题描述

Java中TreeSet方法的计算复杂度是否与AVLTree的计算复杂度相同？

Is the computational complexity of TreeSet methods in Java, same as that of an AVLTree?

具体来说，我想知道以下方法的计算复杂性：
1.add
2.remove
3.first
4.last
5. floor
6.更高

Specifically, I want to know the computational complexity of the following methods: 1.add 2.remove 3.first 4.last 5. floor 6. higher

Java文档的方法描述： http://docs.oracle.com/javase/6/docs/api/java/util /TreeSet.html

Java Doc for method description: http://docs.oracle.com/javase/6/docs/api/java/util/TreeSet.html

对于AVL树，全部是O（logn）？上述TreeSet方法的复杂性是多少？

For an AVL Tree, there are all O(logn)? Whats the complexity of the above TreeSet Methods?

推荐答案

它们都是O（ln n）比较，除了第一个和最后一个是O （1）比较或O（ln N）个节点搜索时间。

They are all O(ln n) comparisons except first and last which are O(1) comparisons or O(ln N) node search time.

这篇关于Java中TreeSet方法的计算复杂性的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！