Java中TreeSet部分视图的size（）复杂度是多少

我想知道TreeSet的部分视图的size()的时间复杂度是多少。

假设我要添加随机数来设置（我不关心重复）：

  final TreeSet tree = new TreeSet(); final Random r = new Random(); final int N = 1000; for ( int i = 0; i < N; i++ ) { tree.add( r.nextInt() ); } 

现在我正在考虑size()调用的复杂性：

  final int M = 100; for ( int i = 0; i  t ) { System.out.println( tree.subSet( t, f ).size() ); } else { System.out.println( tree.subSet( f, t ).size() ); } } 

tree.headSet( t )复杂的tree.headSet( t ) ， tree.tailSet( f )和tree.subSet( f, t )是O（lg N）， set.size()是O（1），但是size()方法呢以上？ 我有一种不好的感觉，它是O（K），其中K是所选子集的大小。

也许如果有一些解决方法来找到集合中某个元素的索引就足够了，因为如果我能得到ti = indexOf(f) ，那么就说O（lg N）比它正是我需要的。

Answer 1

看起来size ()复杂度是O(N) ，因为它可以调用像这样实现的TreeMap.NavigableSubMap.EntrySetView.size () （Oracle JDK 1.7.0_13）：

 public int size() { if (fromStart && toEnd) return m.size(); if (size == -1 || sizeModCount != m.modCount) { sizeModCount = m.modCount; size = 0; Iterator i = iterator(); while (i.hasNext()) { size++; i.next(); } } return size; }