java - NavigableMap 的 floorEntry() 方法的时间复杂度是多少？

Question

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

例如:

如果我有一个具有 n 个间隔的 NavigableMap，并且我使用 map.floorEntry(k) 来获取一些随机的 k，那么会是什么操作执行的时间复杂度？

Answer 1

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

TreeMap 的 Javadoc 只说明了

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations

但是floorEntry()的实现在复杂度上与get()的实现类似。

两者都调用辅助方法(get() 调用 getEntry() 和 floorEntry() 调用 getFloorEntry()) 执行大部分逻辑，两个辅助方法都有一个 while 循环，在每次迭代中前进到左或右 child ，直到它找到它正在寻找的东西或到达叶子。因此所需的时间是树的深度 - 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;
}