我想知道size()
TreeSet 的部分视图的时间复杂度是多少。
假设我正在添加随机数来设置(而且我不关心重复):
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()
调用的复杂性是:
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 )
是O(lg N),tree.tailSet( f )
是O(1),但是上面的方法呢?我有一种不好的感觉,它是 O(K),其中 K 是所选子集的大小。tree.subSet( f, t )
set.size()
size()
也许如果有一些解决方法可以在 set 中找到某个元素的索引就足够了,因为如果我能得到ti = indexOf(f)
,比如说 O(lg N) ,这正是我所需要的。