TreeMap操作的时间复杂度--subMap，headMap，tailMap [英] Time complexity of TreeMap operations- subMap, headMap, tailMap

问题描述

有没有人知道TreeMap操作的时间复杂度，如 - subMap，headMap。 tailMap。

Does anyone know the time complexity of the operations of TreeMap like - subMap, headMap. tailMap.

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

The time complexity of operations like get, put is O(logn). But the javadoc doesnt say much about the complexity for the above operations.

我能想到O（n）的最坏情况复杂性，因为它会通过如果集合包含最后一个元素，则为整个列表。
我们可以确认一下吗？

The worst case complexity I can thinks of O(n) since it will go through the entire list if the set includes the last element. Can we confirm it?

推荐答案

对于那些拥有源代码的问题非常有用，因为有足够的IDE支持您只需浏览实施。查看 TreeMap 可以看出，所有三种方法都是使用 AscendingSubMap的构造函数：

For those questions having the source code on hand is very useful as with sufficient IDE support you can simply browse through the implementation. When looking at the source code of TreeMap it can be seen, that all three methods construct a new map by using the constructor of AscendingSubMap:

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

除了使用超级构造函数将参数传递给class NavigableSubMap ：

Which does nothing else then to pass the parameters up with the super constructor to the class NavigableSubMap:

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

因此所有三种方法都基于以下构造函数：

So all three methods are based on the following constructor:

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）。

All I can see here are invocations to compare for type and assertion checking reasons. Hence, it should be pretty much O(1).

你总是可以在线浏览源代码，但我真的建议获取源文件并将它们链接到您选择的IDE。

You can always browse the source code online, but I really recommend to get the source files and link them to your IDE of choice.

这篇关于TreeMap操作的时间复杂度--subMap，headMap，tailMap的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！