15

subMap、headMapなどのTreeMapの操作の時間の複雑さを知っている人はいますか。テールマップ。

get、put などの操作の時間計算量は O(logn) です。しかし、javadoc は、上記の操作の複雑さについてはあまり述べていません。

セットに最後の要素が含まれている場合、リスト全体を通過するため、最悪の場合の複雑さは O(n) と考えられます。確認できますか？

4

2 に答える 2

13

これらの質問については、ソース コードを手元に用意しておくと非常に便利です。十分な IDE サポートがあれば、実装を参照するだけで済みます。TreeMapのソース コードを見ると、3 つのメソッドすべてが AscendingSubMapのコンストラクターを使用して新しいマップを作成していることがわかります。

public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
                                K toKey,   boolean toInclusive) {
    return new AscendingSubMap(this,
                               false, fromKey, fromInclusive,
                               false, toKey,   toInclusive);
}

スーパーコンストラクターでパラメーターをクラスに渡す以外に何もしませんNavigableSubMap:

super(m, fromStart, lo, loInclusive, toEnd, hi, hiInclusive);

したがって、3 つのメソッドはすべて、次のコンストラクターに基づいています。

NavigableSubMap(TreeMap<K,V> m,
                boolean fromStart, K lo, boolean loInclusive,
                boolean toEnd,     K hi, boolean hiInclusive) {
    if (!fromStart && !toEnd) {
        if (m.compare(lo, hi) > 0)
            throw new IllegalArgumentException("fromKey > toKey");
    } else {
        if (!fromStart) // type check
            m.compare(lo, lo);
        if (!toEnd)
            m.compare(hi, hi);
    }

    this.m = m;
    this.fromStart = fromStart;
    this.lo = lo;
    this.loInclusive = loInclusive;
    this.toEnd = toEnd;
    this.hi = hi;
    this.hiInclusive = hiInclusive;
}

ここで確認できるのはcompare、型とアサーション チェックのための呼び出しだけです。したがって、それはほとんどO(1)である必要があります。

ソース コードはいつでもオンラインで参照できますが、ソース ファイルを入手して、選択した IDE にリンクすることを強くお勧めします。

于 2013-01-12T06:19:58.097 に答える
2

TreeMapのソースを参照して、詳細な実装を取得することができました。

実際にサブマップをどのように取得しているかについてソースコードを詳しく説明すると、次のようになります...

NavigableSubMap の size メソッドを見たら

  public int size() {
        return (fromStart && toEnd) ? m.size() : entrySet().size();
    }

複数の呼び出しでの entrySet() 実装は、最終的に getCeilingEntry() 関数を呼び出します

final Entry<K,V> getCeilingEntry(K key) {
    Entry<K,V> p = root;
    while (p != null) {
        int cmp = compare(key, p.key);
        if (cmp < 0) {
            if (p.left != null)
                p = p.left;
            else
                return p;
        } else if (cmp > 0) {
            if (p.right != null) {
                p = p.right;
            } else {
                Entry<K,V> parent = p.parent;
                Entry<K,V> ch = p;
                while (parent != null && ch == parent.right) {
                    ch = parent;
                    parent = parent.parent;
                }
                return parent;
            }
        } else
            return p;
    }
    return null;
}

SO私は、作成されたサブマップから実際のマップを取得すると思います。時間計算量は O(1) 以上です。

于 2013-01-12T08:27:29.080 に答える