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

Question

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

例如：

如果我有NavigableMapn 个间隔，并且我使用map.floorEntry(k)一些 random k，那么执行操作的时间复杂度是多少？

Answer 1

NavigableMap是一个接口，所以我无法回答该接口的任何实现。不过，落实起来TreeMap，还floorEntry()需要log(n)时间。

JavadocTreeMap仅指出

此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本

但就复杂性而言，的实现floorEntry()与 的实现类似。get()

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