Co to jest złożoność size() dla widoku części TreeSet w Javie

Question

Zastanawiam się, jaka jest złożoność czasu size() dla widoku części TreeSet.

powiedzmy Dodaję liczb losowych, aby ustawić (i nie dbam o 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()); 
    } 

i teraz jestem wodering co jest złożoność dla size() połączeń jak:

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

Złożoność AFAIK tree.headSet(t), tree.tailSet(f) i tree.subSet(f, t) to O (lg N), set.size() to O (1), ale co z powyższymi metodami size()? Mam takie złe przeczucie, że to O (K), gdzie K jest wielkością wybranego podzbioru.

Być może, jeśli istnieje jakiś sposób obejścia indeksu jakiegoś elementu w zestawie, to wystarczy, ponieważ jeśli mogę uzyskać ti = indexOf(f), powiedzmy O (lg N), niż jest to dokładnie to, czego potrzebuję.

Answer 1

Wygląda na złożoność size() jest O(N), ponieważ może to wywołać TreeMap.NavigableSubMap.EntrySetView.size() który jest realizowany tak (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; 
}