如果我已经形成了NavigableMap。 floorEntry()操作执行需要多少时间？是O(1)还是O(logn)？
例如:
如果我有一个n个间隔的NavigableMap，并且对一些随机的map.floorEntry(k)使用k，那么执行该操作的时间复杂度是多少？
最佳答案
NavigableMap是一个接口(interface)，因此对于该接口(interface)的任何实现我都无法回答。但是，对于TreeMap实现，floorEntry()需要log(n)时间。TreeMap的Javadoc仅声明:
但是floorEntry()的实现在复杂性方面类似于get()的实现。
两者都调用执行大多数逻辑的辅助方法(get()调用getEntry()和floorEntry()调用getFloorEntry())，并且这两个辅助方法都有一个while循环，该循环在每次迭代中都前进到左或右子级，直到找到所需的内容为止。为或到达一片叶子。因此，所需的时间是树的深度-O(log(n))。
这是getEntry()和floorEntry()的实现:
/**
* Returns this map's entry for the given key, or {@code null} if the map
* does not contain an entry for the key.
*
* @return this map's entry for the given key, or {@code null} if the map
* does not contain an entry for the key
* @throws ClassCastException if the specified key cannot be compared
* with the keys currently in the map
* @throws NullPointerException if the specified key is null
* and this map uses natural ordering, or its comparator
* does not permit null keys
*/
final Entry<K,V> getEntry(Object key) {
// Offload comparator-based version for sake of performance
if (comparator != null)
return getEntryUsingComparator(key);
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
Entry<K,V> p = root;
while (p != null) {
int cmp = k.compareTo(p.key);
if (cmp < 0)
p = p.left;
else if (cmp > 0)
p = p.right;
else
return p;
}
return null;
}
/**
* Gets the entry corresponding to the specified key; if no such entry
* exists, returns the entry for the greatest key less than the specified
* key; if no such entry exists, returns {@code null}.
*/
final Entry<K,V> getFloorEntry(K key) {
Entry<K,V> p = root;
while (p != null) {
int cmp = compare(key, p.key);
if (cmp > 0) {
if (p.right != null)
p = p.right;
else
return p;
} else if (cmp < 0) {
if (p.left != null) {
p = p.left;
} else {
Entry<K,V> parent = p.parent;
Entry<K,V> ch = p;
while (parent != null && ch == parent.left) {
ch = parent;
parent = parent.parent;
}
return parent;
}
} else
return p;
}
return null;
}