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