Độ phức tạp của kích thước() đối với chế độ xem phần TreeSet trong Java

Question

Tôi tự hỏi độ phức tạp của thời gian là size() đối với phần xem của TreeSet là bao nhiêu.

Hãy nói tôi thêm số ngẫu nhiên để thiết lập (và tôi không quan tâm đến 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()); 
    } 

và bây giờ tôi đang wodering phức tạp cho size() cuộc gọi như là những gì:

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

Độ phức tạp AFAIK của tree.headSet(t), tree.tailSet(f) và tree.subSet(f, t) là O (lg N), set.size() là O (1), nhưng còn về phương pháp size() ở trên? Tôi có cảm giác xấu đến mức đó là O (K) trong đó K là kích thước của tập con được chọn.

Có thể nếu có một số giải pháp để tìm chỉ mục của một số yếu tố trong thiết lập nó sẽ là đủ, bởi vì nếu tôi có thể nhận được ti = indexOf(f), nói O (lg N) hơn là chính xác những gì tôi cần.

Answer 1

Hình như độ phức tạp của size() là O(N), bởi vì nó có thể gọi TreeMap.NavigableSubMap.EntrySetView.size() đó được thực hiện như thế này (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; 
}