Какова сложность size () для представления порций TreeSet в Java
Мне интересно, какова временная сложность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 )
, tree.tailSet( f )
а такжеtree.subSet( f, t )
O (LG N),set.size()
это O (1), но как насчетsize()
методы выше? У меня такое плохое предчувствие, что это O (K), где K - размер выбранного подмножества.
Может быть, если есть какой-то обходной путь для поиска индекса некоторого элемента в наборе, этого будет достаточно, потому что, если я могу получитьti = indexOf(f)
, скажем, O (LG N), чем это именно то, что мне нужно.