JavaのTreeSet部分ビューのsize（）の複雑さは何ですか？

Question

TreeSetの部分ビューのsize()の時間の複雑さは何ですか？

レッツは、私が設定するための乱数を追加している（と私はduplicities気にしない）と言う：

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

、今のようにsize()通話のための複雑さが何であるかをwoderingだ：

final int M = 100; 
    for (int i = 0; i < M; i++) { 
     final int f = r.nextInt(); 
     final int t = r.nextInt(); 
     System.out.println(tree.headSet(t).size()); 
     System.out.println(tree.tailSet(f).size()); 
     if (f > t) { 
      System.out.println(tree.subSet(t, f).size()); 
     } else { 
      System.out.println(tree.subSet(f, t).size()); 
     } 
    } 

AFAIK複雑度tree.headSet(t),tree.tailSet(f)およびtree.subSet(f, t)はO（1g N）であり、set.size()はO（1）であるが、上記の方法は約size()である。私は、Kが選択されたサブセットのサイズであるO（K）というような悪い気持ちを持っています。

もし私がti = indexOf(f)を得ることができれば、それは正確に私が必要とするものよりもO（lg N）を言うことができるので、それは十分であろうセット内のある要素のインデックスを見つけるための回避策があるかもしれません。

Answer 1

それは（OracleのJDK 1.7.0_13）このように実装されているTreeMap.NavigableSubMap.EntrySetView.size()を呼ぶ可能性があるためsize()の複雑さは、O(N)あるように見える：

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; 
}