10

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()上記の方法はどうですか? Kが選択されたサブセットのサイズであるO（K）であることはとても悪い予感です。

たぶん、セット内のいくつかの要素のインデックスを見つけるための回避策があれば、それで十分でしょうti = indexOf(f).O(lg N)としましょう.

4

1 に答える 1

15

次のように実装されているものを呼び出す可能性があるため、size ()の複雑さのように見えます(Oracle JDK 1.7.0_13):O(N)TreeMap.NavigableSubMap.EntrySetView.size ()

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;
}
于 2013-02-07T12:03:12.597 に答える