TreeMap操作的时间复杂性- subMap、headMap、tailMap
TreeMap操作的时间复杂性- subMap、headMap、tailMap
提问于 2013-01-12 14:04:55
有没有人知道像subMap，headMap这样的TreeMap运算的时间复杂度。tailMap。
get、put等操作的时间复杂度为O(logn)。但是javadoc并没有说明上述操作的复杂性。
我能想到的最坏情况复杂度是O(n)，因为如果集合包含最后一个元素，它将遍历整个列表。我们能确认一下吗？
回答 2
Stack Overflow用户
回答已采纳
发布于 2013-01-12 14:19:58
对于这些问题，手头有源代码是非常有用的，因为有了足够的IDE支持，您可以简单地浏览实现。查看TreeMap的源代码可以看出，这三种方法都是通过使用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);
}它不做任何其他事情，然后将参数与超级构造函数一起向上传递给类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，但我真的建议您获取源文件并将它们链接到您选择的集成开发环境。
Stack Overflow用户
发布于 2013-01-12 16:27:29
我能够浏览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)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/14290751
复制相关文章
相似问题
腾讯云开发者
