15

有谁知道 TreeMap 操作的时间复杂度，比如 subMap、headMap。尾图。

get、put 等操作的时间复杂度为 O(logn)。但是 javadoc 并没有过多地说明上述操作的复杂性。

我能想到的最坏情况复杂度 O(n) 因为如果集合包含最后一个元素，它将遍历整个列表。我们可以确认吗？

4

2 回答 2

13

对于那些手头有源代码的问题非常有用，因为有足够的 IDE 支持，您可以简单地浏览实现。查看TreeMap的源代码可以看出，这三个方法都使用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);

所以这三种方法都基于以下构造函数：

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的源代码以获取详细的实现。

如果您详细了解源代码，了解他们实际上是如何获取 subMap 的，它就像这样......

如果你看到 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;
}

所以我想从创建的子地图中获取实际地图；时间复杂度大于 O(1)。

于 2013-01-12T08:27:29.080 回答