- Java 双重比较
- java - 比较器与 Apache BeanComparator
- Objective-C 完成 block 导致额外的方法调用?
- database - RESTful URI 是否应该公开数据库主键?
有谁知道像 subMap、headMap 这样的 TreeMap 操作的时间复杂度。尾图。
get、put等操作的时间复杂度是O(logn)。但是 javadoc 并没有说明上述操作的复杂性。
我能想到的最坏情况复杂度为 O(n),因为如果集合包含最后一个元素,它将遍历整个列表。我们可以确认吗?
最佳答案
对于那些手头有源代码的问题非常有用,因为有足够的 IDE 支持,您可以简单地浏览实现。查看TreeMap的源代码时可以看出,这三种方法都是通过使用constructor of AscendingSubMap构建了一个新的 map 。 :
public NavigableMap<K,V> subMap(K fromKey, boolean fromInclusive,
K toKey, boolean toInclusive) {
return new AscendingSubMap(this,
false, fromKey, fromInclusive,
false, toKey, toInclusive);
}
什么都不做,然后将参数与 super 构造函数一起传递给类 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)。
你总是可以browse the source code online ,但我真的建议获取源文件并将它们链接到您选择的 IDE。
关于java - TreeMap 操作的时间复杂度- subMap, headMap, tailMap,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/14290751/
为什么 Map 类型的 TreeMap 没有定义方法 tailMap 或 headMap。 Map map = new TreeMap<>(); map.tailMap(); //cannot re
我已经实现了几次 NavigableMap,但它似乎总是比应该做的多一些。虽然它是一个非常大的接口(interface),但诸如 java.util.AbstractMap 和 Guava 的 For
有谁知道像 subMap、headMap 这样的 TreeMap 操作的时间复杂度。尾图。 get、put等操作的时间复杂度是O(logn)。但是 javadoc 并没有说明上述操作的复杂性。 我能想
我有使用 SortedMap.tailMap 的 Java 代码.在我移植的代码中,我有 SortedMap = Dictionary .我需要一种在 C# 中复制/模仿 tailMap 的方法。 我
我是一名优秀的程序员,十分优秀!