TreeSet中有序操作的时间复杂度是多少?
java.util.TreeSet
以下操作的时间复杂度是多少?TreeSet中有序操作的时间复杂度是多少?
first()
last()
lower()
higher()
我会假设,这些都是固定的时间,但API不作任何保证。
其实,我一直认为这些操作都将是O(logN)
的一般实现。
为
first()
和last()
是O(1)
TreeSet实现将需要在树分别维持指针最左和最右叶节点。保持这些增加了每次插入的固定成本,并且每次删除都至少保持不变的成本。实际上,这个实现可能会在运行中找到左/右最右节点,这是一个O(logN)
操作。lower()
和higher()
方法必须做与get
相同的工作,因此O(logN)
。
当然,您可以自己检查源代码以查看实际发生的情况。
这将取决于实施。我对JAVA并不是非常熟悉,但似乎所有这些操作都是遍历操作(获取最低元素,获得最高元素,获得更高或更低的元素)。
如果该树实现为Self-Balancing Binary Search Tree(如AVL Tree)或任何其他类型的平衡树结构,那么您将分别查看每个平均树和最坏情况O(log n)时间的操作,以及O(1)的最佳案例。
但是实现被指定为红黑树,所以它不依赖于实现。 – EJP 2011-03-07 01:52:55
看起来像两个第一()和last()将是O(log n)的,而不是O(1)基于其使用TreeSet的默认树形图Implentation(太阳JDK 1.6.0_23):
/**
* 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;
}
我居然抬头看看源代码, 在http://developer.classpath.org/doc/java/util/TreeSet-source.html,first()调用贴图。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:)
我看了看源代码,但是太抽象了。我不确定第一个和最后一个是在哪里实施的。得看看更多。 – signalseeker 2011-03-07 01:12:28
TreeSet在内部使用TreeMap实现,所以大部分逻辑都在'TreeMap.get [First | Last | Lower | Higher] Entry()'中。所有遍历树找到节点,所以Stephen C是正确的,O(log N)。 – SimonC 2011-03-07 02:00:08