Was ist die Komplexität von size() für TreeSet Teilansicht in Java

Question

Ich frage mich, was ist die Zeit Komplexität von size() für Teilansicht von TreeSet.

Lassen Sie sagen, ich bin Zufallszahlen Zugabe zu setzen (und ich kümmere mich nicht um Duplizitäten):

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

und jetzt bin ich wodering was Komplexität für size() Anrufe als:

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 Komplexität von tree.headSet(t), tree.tailSet(f) und tree.subSet(f, t) sind O (LG N), set.size() ist O (1), aber was ist mit size() Methoden oben? Ich habe so ein schlechtes Gefühl, dass es O (K) ist, wo K die Größe der ausgewählten Teilmenge ist.

Vielleicht, wenn es einige Workarounds gibt, um den Index eines Elements im Set zu finden, würde es reichen, denn wenn ich ti = indexOf(f) bekomme, sagen wir O (lg N), dann ist es genau das, was ich brauche.

Answer 1

Sieht aus wie Komplexität der size()O(N) ist, weil es TreeMap.NavigableSubMap.EntrySetView.size() nennen kann, die so (Oracle JDK 1.7.0_13) implementiert:

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