树状图操作的时间复杂度 - 子映射、headMap、tailMap

list java treemap

2022-09-03 14:51:26

有没有人知道树状地图操作的时间复杂度，例如 - 子地图，headMap。尾图。

像 get， put 这样的操作的时间复杂度是 O（logn）。但是javadoc并没有说明上述操作的复杂性。

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

答案 1

对于这些问题，手头有源代码非常有用，因为有了足够的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;
}

我在这里看到的只是对类型和断言检查原因的调用。因此，它应该几乎是O（1）。。compare

您可以随时在线浏览源代码，但我真的建议获取源文件并将其链接到您选择的IDE。

答案 2

我能够浏览TreeMap的源代码以获得详细的实现。

如果你详细地使用源代码，了解他们如何实际获取子地图，就像这样......

如果您看到 NavigableSubMap 的大小方法

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

多次调用中的 entrySet（）实现 final 调用 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）。