NavigableMap的floorEntry（）方法的时间复杂度是多少？

Question

如果我有一个NavigableMap已经形成。将执行floorEntry()操作所需的时间是多少？它会是O(1)还是O(logn)？

例如：

如果我有一个NavigableMap具有n个间隔，我用map.floorEntry(k)一些随机k，会是怎样的操作的执行的时间复杂度？

Answer 1

NavigableMap是一个接口，所以我无法回答该接口的任何实现。但是，对于TreeMap实施，floorEntry()需要log(n)时间。

的TreeMap的Javadoc只说

此实现保证的log（n）时间的containsKey成本，GET，PUT和删除操作

但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; 
}